grove
grove/src/twig.rs
at @13
1//! The grove mark and project twigs, grown from a seed.
2//!
3//! The same generator as the brand page (brand/grove-twig.html in the old grove repo), so a seed
4//! gives the same twig everywhere. A sympodial twig: the leader zigzags, side shoots alternate
5//! and branch once more, every segment keeps a clear zone around it (drawn as a light halo), and
6//! lengths and starting direction come from the seed.
7
8type Pt = [f64; 2];
9
10struct Axis {
11 pts: Vec<Pt>,
12 order: u32,
13 parent: Option<usize>,
14}
15
16const NODES: u32 = 3;
17const ZIGZAG: f64 = 26.0;
18const UPWARD: f64 = 0.04;
19const BRANCH_ANGLE: f64 = 48.0;
20const LATERAL_RATIO: f64 = 0.85;
21const LATERAL_NODES: f64 = 0.9;
22const ORDERS: u32 = 2;
23const ANGLE_JITTER: f64 = 9.0;
24const MIN_LATERALS: usize = 3;
25pub const LINE_WIDTH: f64 = 3.9;
26const KEEPAWAY: f64 = 0.55;
27const MIN_ANGLE: f64 = 28.0;
28const FINAL_GAP: f64 = 3.0;
29const LEN_MIN: f64 = 0.7;
30const LEN_MAX: f64 = 1.35;
31const RAD: f64 = std::f64::consts::PI / 180.0;
32
33/// mulberry32, matching the JavaScript generator bit for bit.
34struct Rng(i32);
35
36impl Rng {
37 fn next(&mut self) -> f64 {
38 self.0 = self.0.wrapping_add(0x6d2b79f5u32 as i32);
39 let s = self.0;
40 let mut t = (s ^ ((s as u32) >> 15) as i32).wrapping_mul(1 | s);
41 t = t.wrapping_add((t ^ ((t as u32) >> 7) as i32).wrapping_mul(61 | t)) ^ t;
42 ((t ^ ((t as u32) >> 14) as i32) as u32) as f64 / 4294967296.0
43 }
44}
45
46// ── Geometry ──────────────────────────────────────────────
47
48fn sign(x: f64) -> f64 {
49 if x > 0.0 { 1.0 } else if x < 0.0 { -1.0 } else { 0.0 }
50}
51fn segments_cross(a: Pt, b: Pt, c: Pt, d: Pt) -> bool {
52 let o = |p: Pt, q: Pt, r: Pt| sign((q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0]));
53 o(a, b, c) * o(a, b, d) < 0.0 && o(c, d, a) * o(c, d, b) < 0.0
54}
55fn pt_seg(p: Pt, a: Pt, b: Pt) -> f64 {
56 let (dx, dy) = (b[0] - a[0], b[1] - a[1]);
57 let l2 = dx * dx + dy * dy;
58 let l2 = if l2 == 0.0 { 1e-9 } else { l2 };
59 let t = (((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / l2).clamp(0.0, 1.0);
60 (p[0] - a[0] - t * dx).hypot(p[1] - a[1] - t * dy)
61}
62fn seg_seg(a: Pt, b: Pt, c: Pt, d: Pt) -> f64 {
63 if segments_cross(a, b, c, d) {
64 return 0.0;
65 }
66 pt_seg(a, c, d).min(pt_seg(b, c, d)).min(pt_seg(c, a, b)).min(pt_seg(d, a, b))
67}
68fn same(p: Pt, q: Pt) -> bool {
69 (p[0] - q[0]).abs() < 1e-6 && (p[1] - q[1]).abs() < 1e-6
70}
71fn angle_between(a: Pt, b: Pt, c: Pt, d: Pt) -> f64 {
72 let u = (b[1] - a[1]).atan2(b[0] - a[0]);
73 let v = (d[1] - c[1]).atan2(d[0] - c[0]);
74 let x = (u - v).abs() / RAD;
75 if x > 180.0 { 360.0 - x } else { x }
76}
77/// A new segment must stay `gap` away from everything it doesn't touch, and leave at least
78/// `min_angle` to segments it shares a point with.
79fn clear(a: Pt, b: Pt, segs: &[(Pt, Pt)], gap: f64, min_angle: f64) -> bool {
80 for &(c, d) in segs {
81 if same(a, c) {
82 if angle_between(a, b, c, d) < min_angle {
83 return false;
84 }
85 continue;
86 }
87 if same(a, d) {
88 if angle_between(a, b, d, c) < min_angle {
89 return false;
90 }
91 continue;
92 }
93 if seg_seg(a, b, c, d) < gap {
94 return false;
95 }
96 }
97 true
98}
99
100// ── Growth ────────────────────────────────────────────────
101
102struct Bud {
103 x: f64,
104 y: f64,
105 ang: f64,
106 len: f64,
107 order: u32,
108 nodes: u32,
109 side: f64,
110 parent: usize,
111}
112
113struct Grower {
114 r: Rng,
115 axes: Vec<Axis>,
116 segs: Vec<(Pt, Pt)>,
117 queue: std::collections::VecDeque<Bud>,
118 lateral_side: f64,
119}
120
121impl Grower {
122 fn jit(&mut self, amt: f64) -> f64 {
123 (self.r.next() - 0.5) * 2.0 * amt
124 }
125
126 // The leader grows to full length first; side buds wait in the queue and fit around it.
127 #[allow(clippy::too_many_arguments)]
128 fn axis(&mut self, mut x: f64, mut y: f64, mut ang: f64, len: f64, order: u32, nodes: u32, mut zig: f64, parent: Option<usize>) {
129 let gap = KEEPAWAY * 10.0;
130 // Axes are grown one at a time, so this one's index is the current count.
131 let me = self.axes.len();
132 let mut pts = vec![[x, y]];
133 for i in 0..nodes {
134 ang += zig * ZIGZAG * if i == 0 { 0.5 } else { 1.0 } + self.jit(ANGLE_JITTER);
135 ang += (-90.0 - ang) * UPWARD;
136 let l = len * (LEN_MIN + self.r.next() * (LEN_MAX - LEN_MIN));
137 let mut placed = None;
138 for off in [0.0, 7.0, -7.0, 14.0, -14.0, 21.0, -21.0, 28.0, -28.0, 36.0, -36.0] {
139 let a2: f64 = ang + off;
140 let (nx, ny) = (x + (a2 * RAD).cos() * l, y + (a2 * RAD).sin() * l);
141 if clear([x, y], [nx, ny], &self.segs, gap, MIN_ANGLE) {
142 placed = Some((nx, ny, a2));
143 break;
144 }
145 }
146 let Some((nx, ny, a2)) = placed else { break };
147 self.segs.push(([x, y], [nx, ny]));
148 (x, y, ang) = (nx, ny, a2);
149 pts.push([x, y]);
150 zig = -zig;
151 if i < nodes - 1 && order < ORDERS && self.r.next() < 1.0 {
152 self.lateral_side = -self.lateral_side;
153 let side = self.lateral_side;
154 let bud_ang = ang + side * (BRANCH_ANGLE + self.jit(ANGLE_JITTER));
155 let bud_nodes = (((nodes - i - 1) as f64) * LATERAL_NODES).round().max(1.0) as u32;
156 self.queue.push_back(Bud { x, y, ang: bud_ang, len: len * LATERAL_RATIO, order: order + 1, nodes: bud_nodes, side, parent: me });
157 }
158 }
159 if pts.len() >= 2 {
160 self.axes.push(Axis { pts, order, parent });
161 }
162 }
163}
164
165fn grow(seed: i32) -> Vec<Axis> {
166 let mut r = Rng(seed);
167 let base_angle = r.next() * 360.0;
168 let first_kink = if r.next() < 0.5 { 1.0 } else { -1.0 };
169 let lateral_side = if r.next() < 0.5 { 1.0 } else { -1.0 };
170 let mut g = Grower { r, axes: Vec::new(), segs: Vec::new(), queue: Default::default(), lateral_side };
171 g.axis(0.0, 0.0, base_angle, 10.0, 0, NODES, first_kink, None);
172 while let Some(b) = g.queue.pop_front() {
173 g.axis(b.x, b.y, b.ang, b.len, b.order, b.nodes, b.side, Some(b.parent));
174 }
175 g.axes
176}
177
178/// One side shoot, what grows from it, and the stretch of stem it grows from: a small shape that
179/// still reads at favicon size. The whole twig if no side shoot branches.
180fn section(axes: Vec<Axis>, seed: i32) -> Vec<Axis> {
181 let has_kids = |i: usize| axes.iter().any(|a| a.parent == Some(i));
182 let roots: Vec<usize> = (0..axes.len()).filter(|&i| axes[i].order == 1 && has_kids(i)).collect();
183 if roots.is_empty() {
184 return axes;
185 }
186 let root = roots[(Rng(seed ^ 0x5eed).next() * roots.len() as f64) as usize];
187 let mut keep = vec![false; axes.len()];
188 keep[root] = true;
189 for i in 0..axes.len() {
190 if axes[i].parent.is_some_and(|p| keep[p]) {
191 keep[i] = true;
192 }
193 }
194 let base = axes[root].pts[0];
195 let stem = axes[root].parent.and_then(|p| {
196 let pts = &axes[p].pts;
197 let at = pts.iter().position(|&q| same(q, base))?;
198 (at > 0).then(|| Axis { pts: vec![pts[at - 1], pts[at]], order: 0, parent: None })
199 });
200 let mut out: Vec<Axis> = stem.into_iter().collect();
201 out.extend(axes.into_iter().enumerate().filter(|(i, _)| keep[*i]).map(|(_, a)| a));
202 out
203}
204
205/// Fit the twig and its halo into the 64×64 box with a 2-unit margin. Returns the scale.
206fn fit(axes: &mut [Axis]) -> (f64, f64) {
207 let all = || axes.iter().flat_map(|a| a.pts.iter());
208 let (mut x0, mut x1, mut y0, mut y1) = (f64::MAX, f64::MIN, f64::MAX, f64::MIN);
209 for p in all() {
210 x0 = x0.min(p[0]);
211 x1 = x1.max(p[0]);
212 y0 = y0.min(p[1]);
213 y1 = y1.max(p[1]);
214 }
215 let halo_r = KEEPAWAY * 10.0;
216 let k = (64.0 - 4.0) / ((x1 - x0).max(y1 - y0).max(1e-6) + halo_r * 2.0);
217 let (cx, cy) = ((x0 + x1) / 2.0, (y0 + y1) / 2.0);
218 for a in axes.iter_mut() {
219 for p in a.pts.iter_mut() {
220 *p = [32.0 + (p[0] - cx) * k, 32.0 + (p[1] - cy) * k];
221 }
222 }
223 let aspect = (x1 - x0).min(y1 - y0) / (x1 - x0).max(y1 - y0);
224 (k, aspect)
225}
226
227// No crossings, enough shoots, clear gaps, no slivers.
228fn usable(seed: i32) -> bool {
229 let mut axes = grow(seed);
230 let (_, aspect) = fit(&mut axes);
231 let segs: Vec<(Pt, Pt, usize)> =
232 axes.iter().enumerate().flat_map(|(ai, ax)| ax.pts.windows(2).map(move |w| (w[0], w[1], ai))).collect();
233 for i in 0..segs.len() {
234 for j in i + 1..segs.len() {
235 if segs[i].2 != segs[j].2 && segments_cross(segs[i].0, segs[i].1, segs[j].0, segs[j].1) {
236 return false;
237 }
238 }
239 }
240 if axes.len() < MIN_LATERALS + 1 {
241 return false;
242 }
243 for i in 0..segs.len() {
244 for j in i + 1..segs.len() {
245 let ((a, b, _), (c, d, _)) = (segs[i], segs[j]);
246 if same(a, c) || same(a, d) || same(b, c) || same(b, d) {
247 let shared = if same(a, c) || same(a, d) { a } else { b };
248 let (p1, q1) = if same(shared, a) { (a, b) } else { (b, a) };
249 let (p2, q2) = if same(shared, c) { (c, d) } else { (d, c) };
250 let ang = angle_between(p1, q1, p2, q2);
251 if ang < MIN_ANGLE && ang > 0.5 {
252 return false;
253 }
254 continue;
255 }
256 if seg_seg(a, b, c, d) < LINE_WIDTH + FINAL_GAP {
257 return false;
258 }
259 }
260 }
261 aspect >= 0.42
262}
263
264// ── Daily ─────────────────────────────────────────────────
265
266fn daily_seed(day: i64) -> i32 {
267 for k in 0..60 {
268 let seed = (day * 7 + k * 104_729) as i32;
269 if usable(seed) {
270 return seed;
271 }
272 }
273 46
274}
275
276/// grove's own mark: one twig, kept. (It's the twig the name letterpress/grove grows; the mark
277/// used to change every day, and this is the one that stayed.)
278pub const MARK: i64 = 49_850;
279
280/// A twig that belongs to a name rather than a day: the same name always grows the same twig.
281pub fn day_for(name: &str) -> i64 {
282 let h = crate::blake3::hash(name.as_bytes());
283 i64::from(u32::from_le_bytes([h[0], h[1], h[2], h[3]]) % 1_000_000)
284}
285
286/// Today's shape: path data for each shoot in a 64×64 box, and the halo's stroke width.
287pub struct Shape {
288 pub shoots: Vec<String>,
289 pub halo_width: f64,
290}
291
292/// A number as JavaScript prints `+n.toFixed(2)`.
293fn num(n: f64) -> String {
294 let s = format!("{n:.2}");
295 let s = s.trim_end_matches('0').trim_end_matches('.');
296 if s == "-0" { "0".into() } else { s.to_string() }
297}
298
299/// A day's twig, or with `part` one section of it.
300pub fn shape(day: i64, part: bool) -> Shape {
301 let seed = daily_seed(day);
302 let mut axes = grow(seed);
303 if part {
304 axes = section(axes, seed);
305 }
306 let (k, _) = fit(&mut axes);
307 let shoots = axes
308 .iter()
309 .map(|a| a.pts.iter().enumerate().map(|(i, p)| format!("{}{} {}", if i == 0 { "M" } else { "L" }, num(p[0]), num(p[1]))).collect())
310 .collect();
311 Shape { shoots, halo_width: (KEEPAWAY * 10.0 * k * 2.0).max(1.0) }
312}
313
314/// An SVG of a day's twig. `halo` and `color` are any CSS colours.
315pub fn svg(day: i64, part: bool, color: &str, halo: &str, line_width: f64, size: Option<u32>) -> String {
316 let s = shape(day, part);
317 let dims = size.map(|n| format!(r#" width="{n}" height="{n}""#)).unwrap_or_default();
318 let mut out = format!(r#"<svg xmlns="http://www.w3.org/2000/svg"{dims} viewBox="0 0 64 64" fill="none" aria-label="grove">"#);
319 for d in &s.shoots {
320 out += &format!(r#"<path d="{d}" stroke="{halo}" stroke-width="{}" stroke-linecap="round" stroke-linejoin="round"/>"#, num(s.halo_width));
321 }
322 for d in &s.shoots {
323 out += &format!(r#"<path d="{d}" stroke="{color}" stroke-width="{line_width}" stroke-linejoin="round"/>"#);
324 }
325 out + "</svg>"
326}
327
328#[cfg(test)]
329mod tests {
330 use super::*;
331
332 #[test]
333 fn rng_matches_javascript() {
334 // mulberry32(1) in JavaScript: 0.6270739405881613, 0.002735721180215478, 0.5274470399599522
335 let mut r = Rng(1);
336 assert_eq!(r.next(), 0.6270739405881613);
337 assert_eq!(r.next(), 0.002735721180215478);
338 assert_eq!(r.next(), 0.5274470399599522);
339 }
340
341 #[test]
342 fn shapes_match_the_brand_generator() {
343 // From ui/src/lib/grove-twig.ts in the old grove repo.
344 assert_eq!(shape(20727, false).shoots.join("|"), "M54.4 15.25L38.26 22.8L20.3 25.23L11.83 34.03|M38.26 22.8L38.6 36.74L35.63 48.75|M20.3 25.23L9.6 17.05|M38.6 36.74L48.58 44.51");
345 assert_eq!(shape(20727, true).shoots.join("|"), "M43.56 11.36L23.67 20.67|M23.67 20.67L24.1 37.84L20.44 52.64|M24.1 37.84L36.39 47.41");
346 assert_eq!(shape(20745, false).shoots.join("|"), "M10.5 27.5L27.86 32.54L36.83 41.51L53.5 48.48|M27.86 32.54L34.76 24.53L48.2 18.34|M36.83 41.51L36.48 52.19|M34.76 24.53L27.31 11.81");
347 }
348
349 #[test]
350 fn every_day_has_a_twig_and_a_section() {
351 for day in 20_700..20_760 {
352 let full = shape(day, false);
353 let part = shape(day, true);
354 assert!(full.shoots.len() >= MIN_LATERALS + 1);
355 assert!(!part.shoots.is_empty() && part.shoots.len() < full.shoots.len());
356 }
357 }
358}