pierrelf.com
web engine - experimental web browser
1//! Glyph rasterization: converts vector outlines to anti-aliased grayscale bitmaps.
2
3use crate::font::tables::glyf::GlyphOutline;
4
5/// A rasterized glyph bitmap.
6#[derive(Debug, Clone, PartialEq, Eq)]
7pub struct GlyphBitmap {
8 /// Width of the bitmap in pixels.
9 pub width: u32,
10 /// Height of the bitmap in pixels.
11 pub height: u32,
12 /// Horizontal offset from origin to left edge of bitmap.
13 pub bearing_x: i32,
14 /// Vertical offset from origin to top edge of bitmap.
15 pub bearing_y: i32,
16 /// 8-bit grayscale coverage data (0 = transparent, 255 = opaque).
17 /// Size is `width * height`.
18 pub data: Vec<u8>,
19}
20
21/// A line segment for the scanline rasterizer.
22#[derive(Debug, Clone, Copy)]
23struct LineSegment {
24 x0: f32,
25 y0: f32,
26 x1: f32,
27 y1: f32,
28}
29
30impl LineSegment {
31 /// Intersects the horizontal line at `y`. Returns `None` if parallel or out of bounds.
32 /// The mathematical intersection `x` is returned along with direction `dir` (+1 for up, -1 for down).
33 fn intersect_horizontal(&self, y: f32) -> Option<(f32, i32)> {
34 // Only intersect if y is strictly between y0 and y1.
35 let (min_y, max_y, dir) = if self.y0 < self.y1 {
36 (self.y0, self.y1, 1)
37 } else {
38 (self.y1, self.y0, -1)
39 };
40
41 if y < min_y || y >= max_y {
42 return None;
43 }
44
45 let t = (y - self.y0) / (self.y1 - self.y0);
46 let x = self.x0 + t * (self.x1 - self.x0);
47 Some((x, dir))
48 }
49}
50
51/// Scale and flatten a glyph outline into reproducible line segments.
52fn flatten_outline(outline: &GlyphOutline, scale: f32) -> Vec<LineSegment> {
53 let mut segments = Vec::new();
54
55 for contour in &outline.contours {
56 if contour.points.is_empty() {
57 continue;
58 }
59
60 let pts = &contour.points;
61
62 // Iterate through implied points.
63 // TrueType defines curves with an implicit on-curve point
64 // halfway between any two consecutive off-curve points.
65 let mut explicit_points = Vec::with_capacity(pts.len() * 2);
66
67 for (i, p) in pts.iter().enumerate() {
68 let next_p = &pts[(i + 1) % pts.len()];
69
70 // Add the current point
71 explicit_points.push((p.x as f32 * scale, p.y as f32 * scale, p.on_curve));
72
73 // If current and next are both off-curve, insert a midpoint
74 if !p.on_curve && !next_p.on_curve {
75 let mx = (p.x as f32 + next_p.x as f32) * 0.5 * scale;
76 let my = (p.y as f32 + next_p.y as f32) * 0.5 * scale;
77 explicit_points.push((mx, my, true));
78 }
79 }
80
81 // Now traverse the explicit points. The path starts with the first point.
82 // But what if the first point is off-curve?
83 // Let's find an on-curve point to start.
84 let start_idx = explicit_points.iter().position(|p| p.2).unwrap_or(0);
85
86 let len = explicit_points.len();
87 let mut i = 0;
88 let mut cur = explicit_points[start_idx];
89
90 // Ensure we loop back to start.
91 while i < len {
92 let next_idx = (start_idx + i + 1) % len;
93 let p1 = explicit_points[next_idx];
94
95 if p1.2 {
96 // Line to next on-curve point
97 segments.push(LineSegment {
98 x0: cur.0,
99 y0: cur.1,
100 x1: p1.0,
101 y1: p1.1,
102 });
103 cur = p1;
104 i += 1;
105 } else {
106 // Quadratic bezier: p1 is control, need next on-curve point
107 let p2_idx = (next_idx + 1) % len;
108 let p2 = explicit_points[p2_idx];
109
110 // Flatten the quadratic bezier curve.
111 flatten_quadratic(cur.0, cur.1, p1.0, p1.1, p2.0, p2.1, &mut segments);
112
113 cur = p2;
114 i += 2;
115 }
116 }
117 }
118
119 segments
120}
121
122/// Flattens a quadratic bézier into line segments using a fixed subdivision.
123fn flatten_quadratic(
124 x0: f32,
125 y0: f32,
126 x1: f32,
127 y1: f32,
128 x2: f32,
129 y2: f32,
130 segments: &mut Vec<LineSegment>,
131) {
132 const STEPS: usize = 8;
133 let mut prev_x = x0;
134 let mut prev_y = y0;
135
136 for i in 1..=STEPS {
137 let t = i as f32 / STEPS as f32;
138 let t_inv = 1.0 - t;
139
140 // Quadratic formula: P = (1-t)^2*P0 + 2t(1-t)*P1 + t^2*P2
141 let cur_x = t_inv * t_inv * x0 + 2.0 * t * t_inv * x1 + t * t * x2;
142 let cur_y = t_inv * t_inv * y0 + 2.0 * t * t_inv * y1 + t * t * y2;
143
144 segments.push(LineSegment {
145 x0: prev_x,
146 y0: prev_y,
147 x1: cur_x,
148 y1: cur_y,
149 });
150
151 prev_x = cur_x;
152 prev_y = cur_y;
153 }
154}
155
156/// Rasterizes a scaled outline into a 0-255 coverage bitmap using 16x16 supersampling.
157pub fn rasterize(outline: &GlyphOutline, scale: f32) -> Option<GlyphBitmap> {
158 if outline.contours.is_empty() {
159 return None;
160 }
161
162 let segments = flatten_outline(outline, scale);
163
164 let x_min = outline.x_min as f32 * scale;
165 let y_min = outline.y_min as f32 * scale;
166 let x_max = outline.x_max as f32 * scale;
167 let y_max = outline.y_max as f32 * scale;
168
169 let bitmap_width = (x_max.ceil() - x_min.floor()) as i32;
170 let bitmap_height = (y_max.ceil() - y_min.floor()) as i32;
171
172 if bitmap_width <= 0 || bitmap_height <= 0 {
173 return None;
174 }
175
176 let bearing_x = x_min.floor() as i32;
177 // Y-axis in TrueType goes UP, but in screen space it goes DOWN.
178 // So the top-left of the bounding box is at y_max.
179 let bearing_y = y_max.ceil() as i32;
180
181 let width = bitmap_width as u32;
182 let height = bitmap_height as u32;
183
184 // 16x16 supersampling => 256 subpixels per pixel.
185 const SUB_PIXELS: u32 = 16;
186 let mut coverage = vec![0u16; (width * height) as usize];
187
188 for sy in 0..(height * SUB_PIXELS) {
189 // TrueType Y goes up. The top pixel is row 0.
190 // Therefore, pixel row `py` corresponds to `bearing_y - py - 1`.
191 // The subpixel offset is from the top of the pixel box going downwards.
192 let sub_y_rel = (sy % SUB_PIXELS) as f32 + 0.5;
193 let py = sy / SUB_PIXELS;
194 let real_y = bearing_y as f32 - (py as f32 + sub_y_rel / SUB_PIXELS as f32);
195
196 // Find intersections.
197 let mut intersections = Vec::with_capacity(32);
198 for seg in &segments {
199 if let Some((x, dir)) = seg.intersect_horizontal(real_y) {
200 intersections.push((x, dir));
201 }
202 }
203
204 // Sort by X coordinate.
205 intersections.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap_or(std::cmp::Ordering::Equal));
206
207 // Traverse intersections to calculate winding and fill pixels.
208 let mut winding = 0;
209 let mut active_start_x = None;
210
211 for (x, dir) in intersections {
212 let prev_winding = winding;
213 winding += dir;
214
215 if prev_winding == 0 && winding != 0 {
216 // Entered shape.
217 active_start_x = Some(x);
218 } else if prev_winding != 0 && winding == 0 {
219 // Exited shape. Fill subpixels between active_start_x and x.
220 if let Some(start_x) = active_start_x {
221 // Map to subpixel coordinates on X axis.
222 let start_sx =
223 ((start_x - bearing_x as f32) * SUB_PIXELS as f32).round() as i32;
224 let end_sx = ((x - bearing_x as f32) * SUB_PIXELS as f32).round() as i32;
225
226 let s_start = start_sx.max(0) as u32;
227 let s_end = (end_sx.max(0) as u32).min(width * SUB_PIXELS);
228
229 for sx in s_start..s_end {
230 let px = sx / SUB_PIXELS;
231 let idx = (py * width + px) as usize;
232 coverage[idx] += 1;
233 }
234 }
235 active_start_x = None;
236 }
237 }
238 }
239
240 // Convert coverage (0-256) to 0-255 u8.
241 let data = coverage.into_iter().map(|c| c.min(255) as u8).collect();
242
243 Some(GlyphBitmap {
244 width,
245 height,
246 bearing_x,
247 bearing_y,
248 data,
249 })
250}
251
252#[cfg(test)]
253mod tests {
254 use super::*;
255 use crate::font::Font;
256
257 fn load_test_font() -> Font {
258 crate::font::load_system_font().expect("failed to load system font")
259 }
260
261 #[test]
262 fn rasterize_basic_glyph() {
263 let font = load_test_font();
264 let head = font.head().unwrap();
265
266 let gid = font.glyph_index(0x0041).unwrap().unwrap(); // 'A'
267 let outline = font.glyph_outline(gid).unwrap().unwrap();
268
269 // 16px size.
270 let scale = 16.0 / head.units_per_em as f32;
271 let bitmap = rasterize(&outline, scale).unwrap();
272
273 assert!(bitmap.width > 0);
274 assert!(bitmap.height > 0);
275 assert_eq!(bitmap.data.len(), (bitmap.width * bitmap.height) as usize);
276
277 // Assert it is anti-aliased (has values other than 0 and 255).
278 let has_intermediate = bitmap.data.iter().any(|&v| v > 0 && v < 255);
279 assert!(has_intermediate, "Bitmap must be anti-aliased");
280
281 // Assert it actually covers some area (has values > 128).
282 let has_coverage = bitmap.data.iter().any(|&v| v > 128);
283 assert!(has_coverage, "Bitmap must have solid pixels");
284 }
285}