ab_glyph_rasterizer/
raster.rs

Help
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.debug_struct("Rasterizer")
296            .field("width", &self.width)
297            .field("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}
ab_glyph_rasterizer/raster.rs

ab_glyph_rasterizer/
raster.rs
