1use crate::platform::{self, abs, atan2, f32x4, sqrt};
2use crate::{Glyph, OutlineBounds};
3use alloc::vec;
4use alloc::vec::*;
5
6#[derive(Copy, Clone, PartialEq, Debug)]
7struct AABB {
8 /// Coordinate of the left-most edge.
9 xmin: f32,
10 /// Coordinate of the right-most edge.
11 xmax: f32,
12 /// Coordinate of the bottom-most edge.
13 ymin: f32,
14 /// Coordinate of the top-most edge.
15 ymax: f32,
16}
17
18impl Default for AABB {
19 fn default() -> Self {
20 AABB {
21 xmin: 0.0,
22 xmax: 0.0,
23 ymin: 0.0,
24 ymax: 0.0,
25 }
26 }
27}
28
29#[derive(Copy, Clone, Debug, PartialEq)]
30struct CubeCurve {
31 a: Point,
32 b: Point,
33 c: Point,
34 d: Point,
35}
36
37impl CubeCurve {
38 const fn new(a: Point, b: Point, c: Point, d: Point) -> CubeCurve {
39 CubeCurve {
40 a,
41 b,
42 c,
43 d,
44 }
45 }
46
47 fn scale(&self, scale: f32) -> CubeCurve {
48 CubeCurve {
49 a: self.a.scale(scale),
50 b: self.b.scale(scale),
51 c: self.c.scale(scale),
52 d: self.d.scale(scale),
53 }
54 }
55
56 fn is_flat(&self, threshold: f32) -> bool {
57 let (d1, d2, d3, d4) = f32x4::new(
58 self.a.distance_squared(self.b),
59 self.b.distance_squared(self.c),
60 self.c.distance_squared(self.d),
61 self.a.distance_squared(self.d),
62 )
63 .sqrt()
64 .copied();
65 (d1 + d2 + d3) < threshold * d4
66 }
67
68 fn split(&self) -> (CubeCurve, CubeCurve) {
69 let q0 = self.a.midpoint(self.b);
70 let q1 = self.b.midpoint(self.c);
71 let q2 = self.c.midpoint(self.d);
72 let r0 = q0.midpoint(q1);
73 let r1 = q1.midpoint(q2);
74 let s0 = r0.midpoint(r1);
75 (CubeCurve::new(self.a, q0, r0, s0), CubeCurve::new(s0, r1, q2, self.d))
76 }
77
78 /// The point at time t in the curve.
79 fn point(&self, t: f32) -> Point {
80 let tm = 1.0 - t;
81 let a = tm * tm * tm;
82 let b = 3.0 * (tm * tm) * t;
83 let c = 3.0 * tm * (t * t);
84 let d = t * t * t;
85
86 let x = a * self.a.x + b * self.b.x + c * self.c.x + d * self.d.x;
87 let y = a * self.a.y + b * self.b.y + c * self.c.y + d * self.d.y;
88 Point::new(x, y)
89 }
90
91 /// The slope of the tangent line at time t.
92 fn slope(&self, t: f32) -> (f32, f32) {
93 let tm = 1.0 - t;
94 let a = 3.0 * (tm * tm);
95 let b = 6.0 * tm * t;
96 let c = 3.0 * (t * t);
97
98 let x = a * (self.b.x - self.a.x) + b * (self.c.x - self.b.x) + c * (self.d.x - self.c.x);
99 let y = a * (self.b.y - self.a.y) + b * (self.c.y - self.b.y) + c * (self.d.y - self.c.y);
100 (x, y)
101 }
102
103 /// The angle of the tangent line at time t in rads.
104 fn angle(&self, t: f32) -> f32 {
105 let (x, y) = self.slope(t);
106 abs(atan2(x, y))
107 }
108}
109
110#[derive(Copy, Clone, Debug, PartialEq)]
111struct QuadCurve {
112 a: Point,
113 b: Point,
114 c: Point,
115}
116
117impl QuadCurve {
118 fn new(a: Point, b: Point, c: Point) -> QuadCurve {
119 QuadCurve {
120 a,
121 b,
122 c,
123 }
124 }
125
126 fn scale(&self, scale: f32) -> QuadCurve {
127 QuadCurve {
128 a: self.a.scale(scale),
129 b: self.b.scale(scale),
130 c: self.c.scale(scale),
131 }
132 }
133
134 fn is_flat(&self, threshold: f32) -> bool {
135 let (d1, d2, d3, _) = f32x4::new(
136 self.a.distance_squared(self.b),
137 self.b.distance_squared(self.c),
138 self.a.distance_squared(self.c),
139 1.0,
140 )
141 .sqrt()
142 .copied();
143 (d1 + d2) < threshold * d3
144 }
145
146 fn split(&self) -> (QuadCurve, QuadCurve) {
147 let q0 = self.a.midpoint(self.b);
148 let q1 = self.b.midpoint(self.c);
149 let r0 = q0.midpoint(q1);
150 (QuadCurve::new(self.a, q0, r0), QuadCurve::new(r0, q1, self.c))
151 }
152
153 /// The point at time t in the curve.
154 fn point(&self, t: f32) -> Point {
155 let tm = 1.0 - t;
156 let a = tm * tm;
157 let b = 2.0 * tm * t;
158 let c = t * t;
159
160 let x = a * self.a.x + b * self.b.x + c * self.c.x;
161 let y = a * self.a.y + b * self.b.y + c * self.c.y;
162 Point::new(x, y)
163 }
164
165 /// The slope of the tangent line at time t.
166 fn slope(&self, t: f32) -> (f32, f32) {
167 let tm = 1.0 - t;
168 let a = 2.0 * tm;
169 let b = 2.0 * t;
170
171 let x = a * (self.b.x - self.a.x) + b * (self.c.x - self.b.x);
172 let y = a * (self.b.y - self.a.y) + b * (self.c.y - self.b.y);
173 (x, y)
174 }
175
176 /// The angle of the tangent line at time t in rads.
177 fn angle(&self, t: f32) -> f32 {
178 let (x, y) = self.slope(t);
179 abs(atan2(x, y))
180 }
181}
182
183#[derive(Copy, Clone, Debug, PartialEq)]
184pub struct Point {
185 /// Absolute X coordinate.
186 pub x: f32,
187 /// Absolute Y coordinate.
188 pub y: f32,
189}
190
191impl Default for Point {
192 fn default() -> Self {
193 Point {
194 x: 0.0,
195 y: 0.0,
196 }
197 }
198}
199
200impl Point {
201 pub const fn new(x: f32, y: f32) -> Point {
202 Point {
203 x,
204 y,
205 }
206 }
207
208 pub fn scale(&self, scale: f32) -> Point {
209 Point {
210 x: self.x * scale,
211 y: self.y * scale,
212 }
213 }
214
215 pub fn distance_squared(&self, other: Point) -> f32 {
216 let x = self.x - other.x;
217 let y = self.y - other.y;
218 x * x + y * y
219 }
220
221 pub fn distance(&self, other: Point) -> f32 {
222 let x = self.x - other.x;
223 let y = self.y - other.y;
224 sqrt(x * x + y * y)
225 }
226
227 pub fn midpoint(&self, other: Point) -> Point {
228 Point {
229 x: (self.x + other.x) / 2.0,
230 y: (self.y + other.y) / 2.0,
231 }
232 }
233}
234
235#[derive(Copy, Clone)]
236pub struct Line {
237 /// X0, Y0, X1, Y1.
238 pub coords: f32x4,
239 /// start_x_nudge, start_y_nudge, end_x_nudge, end_y_nudge.
240 pub nudge: f32x4,
241 /// x_first_adj, y_first_adj, none, none.
242 pub adjustment: f32x4,
243 /// tdx, tdy, dx, dy.
244 pub params: f32x4,
245}
246
247impl Line {
248 pub fn new(start: Point, end: Point) -> Line {
249 // Floor adjustment and nudge: 0.0, 0
250 // Ceil adjustment and nudge: 1.0, 1
251 const FLOOR_NUDGE: u32 = 0;
252 const CEIL_NUDGE: u32 = 1;
253
254 let (x_start_nudge, x_first_adj) = if end.x >= start.x {
255 (FLOOR_NUDGE, 1.0)
256 } else {
257 (CEIL_NUDGE, 0.0)
258 };
259 let (y_start_nudge, y_first_adj) = if end.y >= start.y {
260 (FLOOR_NUDGE, 1.0)
261 } else {
262 (CEIL_NUDGE, 0.0)
263 };
264
265 let x_end_nudge = if end.x > start.x {
266 CEIL_NUDGE
267 } else {
268 FLOOR_NUDGE
269 };
270 let y_end_nudge = if end.y > start.y {
271 CEIL_NUDGE
272 } else {
273 FLOOR_NUDGE
274 };
275
276 let dx = end.x - start.x;
277 let dy = end.y - start.y;
278 let tdx = if dx == 0.0 {
279 core::f32::MAX
280 } else {
281 1.0 / dx
282 };
283 let tdy = 1.0 / dy;
284
285 Line {
286 coords: f32x4::new(start.x, start.y, end.x, end.y),
287 nudge: f32x4::new_u32(x_start_nudge, y_start_nudge, x_end_nudge, y_end_nudge),
288 adjustment: f32x4::new(x_first_adj, y_first_adj, 0.0, 0.0),
289 params: f32x4::new(tdx, tdy, dx, dy),
290 }
291 }
292
293 fn reposition(&mut self, bounds: AABB, reverse: bool) {
294 let (mut x0, mut y0, mut x1, mut y1) = if !reverse {
295 self.coords.copied()
296 } else {
297 let (x0, y0, x1, y1) = self.coords.copied();
298 (x1, y1, x0, y0)
299 };
300
301 x0 -= bounds.xmin;
302 y0 -= bounds.ymax;
303 y0 = abs(y0);
304
305 x1 -= bounds.xmin;
306 y1 -= bounds.ymax;
307 y1 = abs(y1);
308
309 *self = Self::new(Point::new(x0, y0), Point::new(x1, y1));
310 }
311}
312
313#[derive(Clone)]
314pub struct Geometry {
315 v_lines: Vec<Line>,
316 m_lines: Vec<Line>,
317 effective_bounds: AABB,
318 start_point: Point,
319 previous_point: Point,
320 area: f32,
321 reverse_points: bool,
322 max_area: f32,
323}
324
325struct Segment {
326 a: Point,
327 at: f32,
328 c: Point,
329 ct: f32,
330}
331
332impl Segment {
333 const fn new(a: Point, at: f32, c: Point, ct: f32) -> Segment {
334 Segment {
335 a,
336 at,
337 c,
338 ct,
339 }
340 }
341}
342
343impl ttf_parser::OutlineBuilder for Geometry {
344 fn move_to(&mut self, x0: f32, y0: f32) {
345 let next_point = Point::new(x0, y0);
346 self.start_point = next_point;
347 self.previous_point = next_point;
348 }
349
350 fn line_to(&mut self, x0: f32, y0: f32) {
351 let next_point = Point::new(x0, y0);
352 self.push(self.previous_point, next_point);
353 self.previous_point = next_point;
354 }
355
356 fn quad_to(&mut self, x0: f32, y0: f32, x1: f32, y1: f32) {
357 let control_point = Point::new(x0, y0);
358 let next_point = Point::new(x1, y1);
359
360 let curve = QuadCurve::new(self.previous_point, control_point, next_point);
361 let mut stack = vec![Segment::new(self.previous_point, 0.0, next_point, 1.0)];
362 while let Some(seg) = stack.pop() {
363 let bt = (seg.at + seg.ct) * 0.5;
364 let b = curve.point(bt);
365 // This is twice the triangle area
366 let area = (b.x - seg.a.x) * (seg.c.y - seg.a.y) - (seg.c.x - seg.a.x) * (b.y - seg.a.y);
367 if platform::abs(area) > self.max_area {
368 stack.push(Segment::new(seg.a, seg.at, b, bt));
369 stack.push(Segment::new(b, bt, seg.c, seg.ct));
370 } else {
371 self.push(seg.a, seg.c);
372 }
373 }
374
375 self.previous_point = next_point;
376 }
377
378 fn curve_to(&mut self, x0: f32, y0: f32, x1: f32, y1: f32, x2: f32, y2: f32) {
379 let first_control = Point::new(x0, y0);
380 let second_control = Point::new(x1, y1);
381 let next_point = Point::new(x2, y2);
382
383 let curve = CubeCurve::new(self.previous_point, first_control, second_control, next_point);
384 let mut stack = vec![Segment::new(self.previous_point, 0.0, next_point, 1.0)];
385 while let Some(seg) = stack.pop() {
386 let bt = (seg.at + seg.ct) * 0.5;
387 let b = curve.point(bt);
388 // This is twice the triangle area
389 let area = (b.x - seg.a.x) * (seg.c.y - seg.a.y) - (seg.c.x - seg.a.x) * (b.y - seg.a.y);
390 if platform::abs(area) > self.max_area {
391 stack.push(Segment::new(seg.a, seg.at, b, bt));
392 stack.push(Segment::new(b, bt, seg.c, seg.ct));
393 } else {
394 self.push(seg.a, seg.c);
395 }
396 }
397 self.previous_point = next_point;
398 }
399
400 fn close(&mut self) {
401 if self.start_point != self.previous_point {
402 self.push(self.previous_point, self.start_point);
403 }
404 self.previous_point = self.start_point;
405 }
406}
407
408impl Geometry {
409 // Artisanal bespoke hand carved curves
410 pub fn new(scale: f32, units_per_em: f32) -> Geometry {
411 const ERROR_THRESHOLD: f32 = 3.0; // In pixels.
412 let max_area = ERROR_THRESHOLD * 2.0 * (units_per_em / scale);
413
414 Geometry {
415 v_lines: Vec::new(),
416 m_lines: Vec::new(),
417 effective_bounds: AABB {
418 xmin: core::f32::MAX,
419 xmax: core::f32::MIN,
420 ymin: core::f32::MAX,
421 ymax: core::f32::MIN,
422 },
423 start_point: Point::default(),
424 previous_point: Point::default(),
425 area: 0.0,
426 reverse_points: false,
427 max_area,
428 }
429 }
430
431 fn push(&mut self, start: Point, end: Point) {
432 // We're using to_bits here because we only care if they're _exactly_ the same.
433 if start.y.to_bits() != end.y.to_bits() {
434 self.area += (end.y - start.y) * (end.x + start.x);
435 if start.x.to_bits() == end.x.to_bits() {
436 self.v_lines.push(Line::new(start, end));
437 } else {
438 self.m_lines.push(Line::new(start, end));
439 }
440 Self::recalculate_bounds(&mut self.effective_bounds, start.x, start.y);
441 Self::recalculate_bounds(&mut self.effective_bounds, end.x, end.y);
442 }
443 }
444
445 pub(crate) fn finalize(mut self, glyph: &mut Glyph) {
446 if self.v_lines.is_empty() && self.m_lines.is_empty() {
447 self.effective_bounds = AABB::default();
448 } else {
449 self.reverse_points = self.area > 0.0;
450 for line in self.v_lines.iter_mut().chain(self.m_lines.iter_mut()) {
451 line.reposition(self.effective_bounds, self.reverse_points);
452 }
453 self.v_lines.shrink_to_fit();
454 self.m_lines.shrink_to_fit();
455 }
456 glyph.v_lines = self.v_lines;
457 glyph.m_lines = self.m_lines;
458 glyph.bounds = OutlineBounds {
459 xmin: self.effective_bounds.xmin,
460 ymin: self.effective_bounds.ymin,
461 width: self.effective_bounds.xmax - self.effective_bounds.xmin,
462 height: self.effective_bounds.ymax - self.effective_bounds.ymin,
463 };
464 }
465
466 fn recalculate_bounds(bounds: &mut AABB, x: f32, y: f32) {
467 if x < bounds.xmin {
468 bounds.xmin = x;
469 }
470 if x > bounds.xmax {
471 bounds.xmax = x;
472 }
473 if y < bounds.ymin {
474 bounds.ymin = y;
475 }
476 if y > bounds.ymax {
477 bounds.ymax = y;
478 }
479 }
480}
481