text/
outline.rs

1// outline -- glyph outline buffer, path emitter and the operations of synthetic styles
2//                                                                       [src/text/outline.s]
3//
4//   Outline::reset / point / reserve / close / contour / npts / bbox
5//   emit(path, gp, zones)       append the buffer to the path with the gp transform (TrueType
6//                               contours exactly like glyph_path; cubic contours flattened like
7//                               path_cubic); zones = FS_SHARP grid fitting (fit_zones)
8//   embolden(strength)          FreeType FT_Outline_EmboldenXY(strength, strength)
9//   shear(k), transform(from, a, b, c, d), translate(from, dx, dy)
10//   owner_set / owner_is        "prepared" tracking: a box query leaves the untransformed
11//                               outline of (font context, glyph) in the buffer
12//
13// Points f32 x, y (font units, y up) + u8 tags; contour ends u32 (last point index).
14// TrueType contours (OLT_ON / OLT_OFF) follow the implied-midpoint rules; cubic contours
15// (CFF) start with an on-curve point, two OLT_CUBIC points between on-curve points.
16
17use alloc::vec::Vec;
18
19use gfx::path::Path;
20use rt::fx::{cvt, cvtt, maxss, minss, sqrt};
21
22use crate::font::Gp;
23
24pub const OLT_OFF: u8 = 0; // quadratic control point
25pub const OLT_ON: u8 = 1; // on-curve point
26pub const OLT_CUBIC: u8 = 2; // cubic control point
27pub const OL_MAX_PTS: usize = 1 << 20;
28pub const OL_MAX_CONT: usize = 1 << 18;
29const ZONE_MAX: usize = 8;
30const F_DMIN: f32 = -0.9375; // shift only for turns below ~160 degrees
31pub const F_TAN12: f32 = 0.21255656;
32pub const F_INV30: f32 = 0.033333335;
33
34/// FS_SHARP zones: {z (font units), p (px)} ascending
35#[derive(Clone, Copy, Default)]
36pub struct Zones {
37    pub n: usize,
38    pub z: [(f32, f32); ZONE_MAX],
39}
40
41impl Zones {
42    /// descender, 0, x-height, cap height, ascender snapped with sy  [ol_fit_zones]
43    pub fn fit(desc: i32, xh: i32, caph: i32, asc: i32, sy: f32) -> Zones {
44        let mut zn = Zones::default();
45        for v in [desc, 0, xh, caph, asc] {
46            let f = v as f32;
47            if zn.n != 0 && !(f > zn.z[zn.n - 1].0) {
48                continue; // values <= the previous one are skipped
49            }
50            if zn.n >= ZONE_MAX {
51                break;
52            }
53            zn.z[zn.n] = (f, cvt(f * sy) as f32);
54            zn.n += 1;
55        }
56        zn
57    }
58}
59
60#[derive(Default)]
61pub struct Outline {
62    pub pts: Vec<(f32, f32)>,
63    pub tags: Vec<u8>,
64    pub ends: Vec<u32>,
65    cstart: u32,
66    pub err: bool,
67    owner: (u64, u32), // (font context serial, glyph); serial 0 = none
68}
69
70impl Outline {
71    /// empty the buffer (owner cleared)  [ol_reset]
72    pub fn reset(&mut self) {
73        self.pts.clear();
74        self.tags.clear();
75        self.ends.clear();
76        self.cstart = 0;
77        self.err = false;
78        self.owner = (0, u32::MAX);
79    }
80
81    pub fn npts(&self) -> usize {
82        self.pts.len()
83    }
84
85    /// append a point (font units, OLT_*)  [ol_point]
86    pub fn point(&mut self, x: f32, y: f32, tag: u8) -> bool {
87        if self.pts.len() + 1 > OL_MAX_PTS {
88            self.err = true;
89            return false;
90        }
91        self.pts.push((x, y));
92        self.tags.push(tag);
93        true
94    }
95
96    /// append n points (0, 0, OLT_OFF) to be filled in; the index of the first  [ol_reserve]
97    pub fn reserve(&mut self, n: usize) -> Option<usize> {
98        let first = self.pts.len();
99        if first + n > OL_MAX_PTS {
100            self.err = true;
101            return None;
102        }
103        self.pts.resize(first + n, (0.0, 0.0));
104        self.tags.resize(first + n, 0);
105        Some(first)
106    }
107
108    /// end the current contour  [ol_close]
109    pub fn close(&mut self) {
110        let n = self.pts.len() as u32;
111        if n > self.cstart {
112            self.contour(n - 1);
113        }
114    }
115
116    /// end a contour at point index last (last < cstart: empty, ignored)  [ol_contour]
117    pub fn contour(&mut self, last: u32) -> bool {
118        if last as usize >= self.pts.len() {
119            self.err = true;
120            return false;
121        }
122        if last < self.cstart {
123            return true;
124        }
125        if self.ends.len() >= OL_MAX_CONT {
126            self.err = true;
127            return false;
128        }
129        self.ends.push(last);
130        self.cstart = last + 1;
131        true
132    }
133
134    pub fn owner_set(&mut self, serial: u64, glyph: u32) {
135        self.owner = (serial, glyph);
136    }
137
138    pub fn owner_is(&self, serial: u64, glyph: u32) -> bool {
139        self.owner == (serial, glyph)
140    }
141
142    /// control box {xmin, ymin, xmax, ymax} (floor / ceil, clamped to +-1e6)  [ol_box]
143    pub fn bbox(&self) -> Option<[i32; 4]> {
144        let first = *self.pts.first()?;
145        let (mut x0, mut y0, mut x1, mut y1) = (first.0, first.1, first.0, first.1);
146        for &(x, y) in &self.pts {
147            x0 = minss(x0, x);
148            x1 = maxss(x1, x);
149            y0 = minss(y0, y);
150            y1 = maxss(y1, y);
151        }
152        let mut b = [0i32; 4];
153        for (i, v) in [x0, y0, x1, y1].into_iter().enumerate() {
154            let v = minss(maxss(v, -1_000_000.0), 1_000_000.0);
155            let mut t = cvtt(v);
156            let tf = t as f32;
157            if i < 2 {
158                if tf > v {
159                    t -= 1; // floor
160                }
161            } else if !(tf >= v) {
162                t += 1; // ceil
163            }
164            b[i] = t;
165        }
166        Some(b)
167    }
168
169    /// x += y * k  [ol_shear]
170    pub fn shear(&mut self, k: f32) {
171        for p in self.pts.iter_mut() {
172            p.0 = p.1 * k + p.0;
173        }
174    }
175
176    /// points from..n: (x, y) -> (a x + c y, b x + d y)  [ol_transform]
177    pub fn transform(&mut self, from: usize, a: f32, b: f32, c: f32, d: f32) {
178        let from = from.min(self.pts.len());
179        for p in self.pts[from..].iter_mut() {
180            let (x, y) = *p;
181            *p = (x * a + y * c, x * b + y * d);
182        }
183    }
184
185    /// points from..n += (dx, dy)  [ol_translate]
186    pub fn translate(&mut self, from: usize, dx: f32, dy: f32) {
187        let from = from.min(self.pts.len());
188        for p in self.pts[from..].iter_mut() {
189            p.0 = p.0 + dx;
190            p.1 = p.1 + dy;
191        }
192    }
193
194    /// FreeType FT_Outline_EmboldenXY(strength, strength): every edge moves outwards by
195    /// strength / 2, the glyph grows up / right by strength  [ol_embolden]
196    pub fn embolden(&mut self, strength: f32) {
197        let xs = strength * 0.5;
198        if xs == 0.0 {
199            return;
200        }
201        // orientation: area = sum (y_cur - y_prev) * (x_cur + x_prev)
202        let mut area = 0.0f32;
203        let mut first = 0usize;
204        for &e in &self.ends {
205            let last = e as usize;
206            let (mut px, mut py) = self.pts[last];
207            for i in first..=last {
208                let (x, y) = self.pts[i];
209                area = area + (y - py) * (px + x);
210                px = x;
211                py = y;
212            }
213            first = last + 1;
214        }
215        if !(area < 0.0 || area > 0.0) {
216            return; // no orientation (or NaN): leave it
217        }
218        let tt = !(area >= 0.0); // area < 0: TrueType (clockwise)
219        let pts = &mut self.pts;
220        let mut first = 0usize;
221        for &e in &self.ends {
222            let last = e as usize;
223            let (mut in_x, mut in_y, mut l_in) = (0.0f32, 0.0f32, 0.0f32);
224            let (mut anc_x, mut anc_y, mut l_anc) = (0.0f32, 0.0f32, 0.0f32);
225            let mut i = last;
226            let mut j = first;
227            let mut k: isize = -1;
228            while j != i && i as isize != k {
229                let (out_x, out_y, l_out);
230                if j as isize != k {
231                    let ox = pts[j].0 - pts[i].0;
232                    let oy = pts[j].1 - pts[i].1;
233                    let l = sqrt(ox * ox + oy * oy);
234                    if !(l > 0.0) {
235                        // zero length: next j
236                        j = if j < last { j + 1 } else { first };
237                        continue;
238                    }
239                    out_x = ox / l;
240                    out_y = oy / l;
241                    l_out = l;
242                } else {
243                    out_x = anc_x;
244                    out_y = anc_y;
245                    l_out = l_anc;
246                }
247                if !(l_in < 0.0 || l_in > 0.0) {
248                    // first segment (ucomiss + je: zero or unordered)
249                    i = j;
250                } else {
251                    if k < 0 {
252                        k = i as isize;
253                        anc_x = in_x;
254                        anc_y = in_y;
255                        l_anc = l_in;
256                    }
257                    let d0 = in_x * out_x + in_y * out_y;
258                    let (mut sx, mut sy) = (0.0f32, 0.0f32);
259                    if d0 > F_DMIN {
260                        let d = d0 + 1.0;
261                        sx = in_y + out_y;
262                        sy = in_x + out_x;
263                        let mut q = out_x * in_y - out_y * in_x;
264                        if tt {
265                            sx = f32::from_bits(sx.to_bits() ^ 0x8000_0000);
266                            q = f32::from_bits(q.to_bits() ^ 0x8000_0000);
267                        } else {
268                            sy = f32::from_bits(sy.to_bits() ^ 0x8000_0000);
269                        }
270                        let l = minss(l_in, l_out);
271                        if !(xs * q > l * d) {
272                            sx = sx * xs / d;
273                            sy = sy * xs / d;
274                        } else {
275                            sx = sx * l / q;
276                            sy = sy * l / q;
277                        }
278                    }
279                    sx = sx + xs;
280                    sy = sy + xs;
281                    while i != j {
282                        pts[i].0 = pts[i].0 + sx;
283                        pts[i].1 = pts[i].1 + sy;
284                        i = if i < last { i + 1 } else { first };
285                    }
286                }
287                in_x = out_x;
288                in_y = out_y;
289                l_in = l_out;
290                j = if j < last { j + 1 } else { first };
291            }
292            first = last + 1;
293        }
294    }
295
296    /// append every contour to the path (gp transform, composite offset dx / dy honoured;
297    /// zones: FS_SHARP vertical fitting)  [ol_emit]
298    pub fn emit(&self, path: &mut Path, gp: &Gp, zones: Option<&Zones>) {
299        let dxf = gp.dx as f32;
300        let dyf = gp.dy as f32;
301        let load = |i: usize| -> (f32, f32) {
302            let (x, y) = self.pts[i];
303            let x = (x + dxf) * gp.sx + gp.x;
304            let y = y + dyf;
305            let yp = match zones {
306                None => y * gp.sy,
307                Some(zn) => fit_y(zn, y, gp.sy),
308            };
309            (x, gp.y - yp)
310        };
311        let tags = &self.tags;
312        let mut first = 0usize;
313        for &e in &self.ends {
314            let last = e as usize;
315            if last + 1 <= first {
316                first = last + 1;
317                continue;
318            }
319            let n = last - first + 1;
320            if tags[first..=last].contains(&OLT_CUBIC) {
321                self.emit_cubic(path, &load, first, last, n);
322                first = last + 1;
323                continue;
324            }
325            // TrueType contour (the glyph_path walk)
326            let (start, mut next, mut left);
327            if tags[first] & OLT_ON != 0 {
328                start = load(first);
329                next = first + 1;
330                left = n - 1;
331            } else if tags[last] & OLT_ON != 0 {
332                start = load(last);
333                next = first;
334                left = n - 1;
335            } else {
336                let a = load(last);
337                let b = load(first);
338                start = ((b.0 + a.0) * 0.5, (b.1 + a.1) * 0.5);
339                next = first;
340                left = n;
341            }
342            path.move_f(start.0, start.1);
343            let mut pending: Option<(f32, f32)> = None;
344            while left > 0 {
345                left -= 1;
346                let i = next;
347                next += 1;
348                let p = load(i);
349                if tags[i] & OLT_ON != 0 {
350                    match pending.take() {
351                        Some(c) => path.quad_f(c.0, c.1, p.0, p.1),
352                        None => path.line_f(p.0, p.1),
353                    }
354                } else {
355                    if let Some(c) = pending {
356                        path.quad_f(c.0, c.1, (p.0 + c.0) * 0.5, (p.1 + c.1) * 0.5);
357                    }
358                    pending = Some(p);
359                }
360            }
361            if let Some(c) = pending {
362                path.quad_f(c.0, c.1, start.0, start.1);
363            }
364            path.close();
365            first = last + 1;
366        }
367    }
368
369    // a cubic contour: start at the first on-curve point, n steps around
370    fn emit_cubic(&self, path: &mut Path, load: &dyn Fn(usize) -> (f32, f32), first: usize, last: usize, n: usize) {
371        let tags = &self.tags;
372        let Some(s) = (first..=last).find(|&i| tags[i] & OLT_ON != 0) else { return };
373        let start = load(s);
374        path.move_f(start.0, start.1);
375        let mut cur = start;
376        let mut npend = 0;
377        let (mut c1, mut c2) = ((0.0f32, 0.0f32), (0.0f32, 0.0f32));
378        let mut idx = s;
379        for _ in 0..n {
380            idx = if idx + 1 <= last { idx + 1 } else { first };
381            let p = load(idx);
382            if tags[idx] & OLT_ON == 0 {
383                if npend == 0 {
384                    c1 = p;
385                    npend = 1;
386                } else {
387                    c2 = p;
388                    npend = 2;
389                }
390                continue;
391            }
392            match npend {
393                0 => path.line_f(p.0, p.1),
394                1 => path.quad_f(c1.0, c1.1, p.0, p.1),
395                _ => cubic(path, [cur.0, cur.1, c1.0, c1.1, c2.0, c2.1, p.0, p.1]),
396            }
397            npend = 0;
398            cur = p;
399        }
400        path.close();
401    }
402}
403
404// the zone mapping of FS_SHARP: piecewise linear through the snapped zones (pixels, y up)
405fn fit_y(zn: &Zones, y: f32, sy: f32) -> f32 {
406    let z = &zn.z;
407    if !(y > z[0].0) {
408        return (y - z[0].0) * sy + z[0].1; // below the first zone: slope sy
409    }
410    let mut k = 0;
411    let mut left = zn.n;
412    loop {
413        left -= 1;
414        if left == 0 {
415            return (y - z[k].0) * sy + z[k].1; // above the last zone
416        }
417        if !(y > z[k + 1].0) {
418            // p0 + (y - z0) * (p1 - p0) / (z1 - z0)
419            return (y - z[k].0) * (z[k + 1].1 - z[k].1) / (z[k + 1].0 - z[k].0) + z[k].1;
420        }
421        k += 1;
422    }
423}
424
425/// flatten the cubic {p0, c1, c2, p3} (device px; p0 is the current point) into the path,
426/// the subdivision of path_cubic (tolerance 0.2 px)  [ol_cubic]
427pub fn cubic(path: &mut Path, p: [f32; 8]) {
428    let ax = p[0] - (p[2] + p[2]) + p[4];
429    let ay = p[1] - (p[3] + p[3]) + p[5];
430    let m1 = sqrt(ax * ax + ay * ay);
431    let bx = p[2] - (p[4] + p[4]) + p[6];
432    let by = p[3] - (p[5] + p[5]) + p[7];
433    let m2 = maxss(sqrt(bx * bx + by * by), m1);
434    let v = minss(sqrt(m2 * 3.75), 128.0);
435    let mut n = cvtt(v);
436    if !(n as f32 >= v) {
437        n += 1;
438    }
439    let n = n.max(1);
440    for i in 1..=n {
441        if i == n {
442            path.line_f(p[6], p[7]);
443            break;
444        }
445        let t = i as f32 / n as f32;
446        let u = 1.0 - t;
447        let uu = u * u;
448        let b0 = uu * u;
449        let b1 = uu * t * 3.0;
450        let tt = t * t;
451        let b2 = tt * u * 3.0;
452        let b3 = tt * t;
453        let x = p[0] * b0 + p[2] * b1 + p[4] * b2 + p[6] * b3;
454        let y = p[1] * b0 + p[3] * b1 + p[5] * b2 + p[7] * b3;
455        path.line_f(x, y);
456    }
457}
text/outline.rs

text/
outline.rs
