1// Forked/repurposed from `font-rs` code: https://github.com/raphlinus/font-rs
2// Copyright 2015 Google Inc. All rights reserved.
3//
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at
7//
8// http://www.apache.org/licenses/LICENSE-2.0
9//
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15//
16// Modifications copyright (C) 2020 Alex Butler
17//
18// Cubic bezier drawing adapted from stb_truetype: https://github.com/nothings/stb
19#[cfg(all(feature = "libm", not(feature = "std")))]
20use crate::nostd_float::FloatExt;
21#[cfg(not(feature = "std"))]
22use alloc::vec::Vec;
23
24use crate::geometry::{lerp, Point};
25
26type DrawLineFn = unsafe fn(&mut Rasterizer, Point, Point);
27
28/// Coverage rasterizer for lines, quadratic & cubic beziers.
29pub struct Rasterizer {
30 width: usize,
31 height: usize,
32 a: Vec<f32>,
33 draw_line_fn: DrawLineFn,
34}
35
36impl Rasterizer {
37 /// Allocates a new rasterizer that can draw onto a `width` x `height` alpha grid.
38 ///
39 /// ```
40 /// use ab_glyph_rasterizer::Rasterizer;
41 /// let mut rasterizer = Rasterizer::new(14, 38);
42 /// ```
43 pub fn new(width: usize, height: usize) -> Self {
44 Self {
45 width,
46 height,
47 a: vec![0.0; width * height + 4],
48 draw_line_fn: optimal_draw_line_fn(),
49 }
50 }
51
52 /// Resets the rasterizer to an empty `width` x `height` alpha grid. This method behaves as if
53 /// the Rasterizer were re-created, with the advantage of not allocating if the total number of
54 /// pixels of the grid does not increase.
55 ///
56 /// ```
57 /// # use ab_glyph_rasterizer::Rasterizer;
58 /// # let mut rasterizer = Rasterizer::new(14, 38);
59 /// rasterizer.reset(12, 24);
60 /// assert_eq!(rasterizer.dimensions(), (12, 24));
61 /// ```
62 pub fn reset(&mut self, width: usize, height: usize) {
63 self.width = width;
64 self.height = height;
65 self.a.truncate(0);
66 self.a.resize(width * height + 4, 0.0);
67 }
68
69 /// Clears the rasterizer. This method behaves as if the Rasterizer were re-created with the same
70 /// dimensions, but does not perform an allocation.
71 ///
72 /// ```
73 /// # use ab_glyph_rasterizer::Rasterizer;
74 /// # let mut rasterizer = Rasterizer::new(14, 38);
75 /// rasterizer.clear();
76 /// ```
77 pub fn clear(&mut self) {
78 for px in &mut self.a {
79 *px = 0.0;
80 }
81 }
82
83 /// Returns the dimensions the rasterizer was built to draw to.
84 ///
85 /// ```
86 /// # use ab_glyph_rasterizer::*;
87 /// let rasterizer = Rasterizer::new(9, 8);
88 /// assert_eq!((9, 8), rasterizer.dimensions());
89 /// ```
90 pub fn dimensions(&self) -> (usize, usize) {
91 (self.width, self.height)
92 }
93
94 /// Adds a straight line from `p0` to `p1` to the outline.
95 ///
96 /// ```
97 /// # use ab_glyph_rasterizer::*;
98 /// # let mut rasterizer = Rasterizer::new(9, 8);
99 /// rasterizer.draw_line(point(0.0, 0.48), point(1.22, 0.48));
100 /// ```
101 pub fn draw_line(&mut self, p0: Point, p1: Point) {
102 unsafe { (self.draw_line_fn)(self, p0, p1) }
103 }
104
105 #[inline(always)] // must inline for simd versions
106 fn draw_line_scalar(&mut self, p0: Point, p1: Point) {
107 if (p0.y - p1.y).abs() <= core::f32::EPSILON {
108 return;
109 }
110 let (dir, p0, p1) = if p0.y < p1.y {
111 (1.0, p0, p1)
112 } else {
113 (-1.0, p1, p0)
114 };
115 let dxdy = (p1.x - p0.x) / (p1.y - p0.y);
116 let mut x = p0.x;
117 let y0 = p0.y as usize; // note: implicit max of 0 because usize
118 if p0.y < 0.0 {
119 x -= p0.y * dxdy;
120 }
121 for y in y0..self.height.min(p1.y.ceil() as usize) {
122 let linestart = y * self.width;
123 let dy = ((y + 1) as f32).min(p1.y) - (y as f32).max(p0.y);
124 let xnext = x + dxdy * dy;
125 let d = dy * dir;
126 let (x0, x1) = if x < xnext { (x, xnext) } else { (xnext, x) };
127 let x0floor = x0.floor();
128 let x0i = x0floor as i32;
129 let x1ceil = x1.ceil();
130 let x1i = x1ceil as i32;
131 if x1i <= x0i + 1 {
132 let xmf = 0.5 * (x + xnext) - x0floor;
133 let linestart_x0i = linestart as isize + x0i as isize;
134 if linestart_x0i < 0 {
135 continue; // oob index
136 }
137 self.a[linestart_x0i as usize] += d - d * xmf;
138 self.a[linestart_x0i as usize + 1] += d * xmf;
139 } else {
140 let s = (x1 - x0).recip();
141 let x0f = x0 - x0floor;
142 let a0 = 0.5 * s * (1.0 - x0f) * (1.0 - x0f);
143 let x1f = x1 - x1ceil + 1.0;
144 let am = 0.5 * s * x1f * x1f;
145 let linestart_x0i = linestart as isize + x0i as isize;
146 if linestart_x0i < 0 {
147 continue; // oob index
148 }
149 self.a[linestart_x0i as usize] += d * a0;
150 if x1i == x0i + 2 {
151 self.a[linestart_x0i as usize + 1] += d * (1.0 - a0 - am);
152 } else {
153 let a1 = s * (1.5 - x0f);
154 self.a[linestart_x0i as usize + 1] += d * (a1 - a0);
155 for xi in x0i + 2..x1i - 1 {
156 self.a[linestart + xi as usize] += d * s;
157 }
158 let a2 = a1 + (x1i - x0i - 3) as f32 * s;
159 self.a[linestart + (x1i - 1) as usize] += d * (1.0 - a2 - am);
160 }
161 self.a[linestart + x1i as usize] += d * am;
162 }
163 x = xnext;
164 }
165 }
166
167 /// Adds a quadratic Bézier curve from `p0` to `p2` to the outline using `p1` as the control.
168 ///
169 /// ```
170 /// # use ab_glyph_rasterizer::*;
171 /// # let mut rasterizer = Rasterizer::new(14, 38);
172 /// rasterizer.draw_quad(point(6.2, 34.5), point(7.2, 34.5), point(9.2, 34.0));
173 /// ```
174 pub fn draw_quad(&mut self, p0: Point, p1: Point, p2: Point) {
175 let devx = p0.x - 2.0 * p1.x + p2.x;
176 let devy = p0.y - 2.0 * p1.y + p2.y;
177 let devsq = devx * devx + devy * devy;
178 if devsq < 0.333 {
179 self.draw_line(p0, p2);
180 return;
181 }
182 let tol = 3.0;
183 let n = 1 + (tol * devsq).sqrt().sqrt().floor() as usize;
184 let mut p = p0;
185 let nrecip = (n as f32).recip();
186 let mut t = 0.0;
187 for _i in 0..n - 1 {
188 t += nrecip;
189 let pn = lerp(t, lerp(t, p0, p1), lerp(t, p1, p2));
190 self.draw_line(p, pn);
191 p = pn;
192 }
193 self.draw_line(p, p2);
194 }
195
196 /// Adds a cubic Bézier curve from `p0` to `p3` to the outline using `p1` as the control
197 /// at the beginning of the curve and `p2` at the end of the curve.
198 ///
199 /// ```
200 /// # use ab_glyph_rasterizer::*;
201 /// # let mut rasterizer = Rasterizer::new(12, 20);
202 /// rasterizer.draw_cubic(
203 /// point(10.3, 16.4),
204 /// point(8.6, 16.9),
205 /// point(7.7, 16.5),
206 /// point(8.2, 15.2),
207 /// );
208 /// ```
209 pub fn draw_cubic(&mut self, p0: Point, p1: Point, p2: Point, p3: Point) {
210 self.tesselate_cubic(p0, p1, p2, p3, 0);
211 }
212
213 // stb_truetype style cubic approximation by lines.
214 fn tesselate_cubic(&mut self, p0: Point, p1: Point, p2: Point, p3: Point, n: u8) {
215 // ...I'm not sure either ¯\_(ツ)_/¯
216 const OBJSPACE_FLATNESS: f32 = 0.35;
217 const OBJSPACE_FLATNESS_SQUARED: f32 = OBJSPACE_FLATNESS * OBJSPACE_FLATNESS;
218 const MAX_RECURSION_DEPTH: u8 = 16;
219
220 let longlen = p0.distance_to(p1) + p1.distance_to(p2) + p2.distance_to(p3);
221 let shortlen = p0.distance_to(p3);
222 let flatness_squared = longlen * longlen - shortlen * shortlen;
223
224 if n < MAX_RECURSION_DEPTH && flatness_squared > OBJSPACE_FLATNESS_SQUARED {
225 let p01 = lerp(0.5, p0, p1);
226 let p12 = lerp(0.5, p1, p2);
227 let p23 = lerp(0.5, p2, p3);
228
229 let pa = lerp(0.5, p01, p12);
230 let pb = lerp(0.5, p12, p23);
231
232 let mp = lerp(0.5, pa, pb);
233
234 self.tesselate_cubic(p0, p01, pa, mp, n + 1);
235 self.tesselate_cubic(mp, pb, p23, p3, n + 1);
236 } else {
237 self.draw_line(p0, p3);
238 }
239 }
240
241 /// Run a callback for each pixel `index` & `alpha`, with indices in `0..width * height`.
242 ///
243 /// An `alpha` coverage value of `0.0` means the pixel is not covered at all by the glyph,
244 /// whereas a value of `1.0` (or greater) means the pixel is totally covered.
245 ///
246 /// ```
247 /// # use ab_glyph_rasterizer::*;
248 /// # let (width, height) = (1, 1);
249 /// # let mut rasterizer = Rasterizer::new(width, height);
250 /// let mut pixels = vec![0u8; width * height];
251 /// rasterizer.for_each_pixel(|index, alpha| {
252 /// pixels[index] = (alpha * 255.0) as u8;
253 /// });
254 /// ```
255 pub fn for_each_pixel<O: FnMut(usize, f32)>(&self, mut px_fn: O) {
256 let mut acc = 0.0;
257 self.a[..self.width * self.height]
258 .iter()
259 .enumerate()
260 .for_each(|(idx, c)| {
261 acc += c;
262 px_fn(idx, acc.abs());
263 });
264 }
265
266 /// Run a callback for each pixel x position, y position & alpha.
267 ///
268 /// Convenience wrapper for [`Rasterizer::for_each_pixel`].
269 ///
270 /// ```
271 /// # use ab_glyph_rasterizer::*;
272 /// # let mut rasterizer = Rasterizer::new(1, 1);
273 /// # struct Img;
274 /// # impl Img { fn set_pixel(&self, x: u32, y: u32, a: u8) {} }
275 /// # let image = Img;
276 /// rasterizer.for_each_pixel_2d(|x, y, alpha| {
277 /// image.set_pixel(x, y, (alpha * 255.0) as u8);
278 /// });
279 /// ```
280 pub fn for_each_pixel_2d<O: FnMut(u32, u32, f32)>(&self, mut px_fn: O) {
281 let width32 = self.width as u32;
282 self.for_each_pixel(|idx, alpha| px_fn(idx as u32 % width32, idx as u32 / width32, alpha));
283 }
284}
285
286/// ```
287/// let rasterizer = ab_glyph_rasterizer::Rasterizer::new(3, 4);
288/// assert_eq!(
289/// &format!("{:?}", rasterizer),
290/// "Rasterizer { width: 3, height: 4 }"
291/// );
292/// ```
293impl core::fmt::Debug for Rasterizer {
294 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
295 f&mut DebugStruct<'_, '_>.debug_struct("Rasterizer")
296 .field("width", &self.width)
297 .field(name:"height", &self.height)
298 .finish()
299 }
300}
301
302#[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
303#[target_feature(enable = "avx2")]
304unsafe fn draw_line_avx2(rast: &mut Rasterizer, p0: Point, p1: Point) {
305 rast.draw_line_scalar(p0, p1)
306}
307
308#[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
309#[target_feature(enable = "sse4.2")]
310unsafe fn draw_line_sse4_2(rast: &mut Rasterizer, p0: Point, p1: Point) {
311 rast.draw_line_scalar(p0, p1)
312}
313
314/// Return most optimal `DrawLineFn` impl.
315///
316/// With feature `std` on x86/x86_64 will use one-time runtime detection
317/// to pick the best SIMD impl. Otherwise uses a scalar version.
318fn optimal_draw_line_fn() -> DrawLineFn {
319 unsafe {
320 // safe as write synchronised by Once::call_once or no-write
321 static mut DRAW_LINE_FN: DrawLineFn = Rasterizer::draw_line_scalar;
322
323 #[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
324 {
325 static INIT: std::sync::Once = std::sync::Once::new();
326 INIT.call_once(|| {
327 // runtime detect optimal simd impls
328 if is_x86_feature_detected!("avx2") {
329 DRAW_LINE_FN = draw_line_avx2
330 } else if is_x86_feature_detected!("sse4.2") {
331 DRAW_LINE_FN = draw_line_sse4_2
332 }
333 });
334 }
335
336 DRAW_LINE_FN
337 }
338}
339