ab_glyph_rasterizer/
raster.rs

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        /// Does `self.a[$lhs] += $rhs` except if $lhs is oob `continue` instead of panic.
108        macro_rules! add_assign_a_idx {
109            ($lhs:expr, $rhs:expr) => {
110                match self.a.get_mut($lhs) {
111                    Some(v) => *v += $rhs,
112                    None => continue,
113                };
114            };
115        }
116
117        if (p0.y - p1.y).abs() <= f32::EPSILON {
118            return;
119        }
120        let (dir, p0, p1) = if p0.y < p1.y {
121            (1.0, p0, p1)
122        } else {
123            (-1.0, p1, p0)
124        };
125        let dxdy = (p1.x - p0.x) / (p1.y - p0.y);
126        let mut x = p0.x;
127        let y0 = p0.y as usize; // note: implicit max of 0 because usize
128        if p0.y < 0.0 {
129            x -= p0.y * dxdy;
130        }
131        for y in y0..self.height.min(p1.y.ceil() as usize) {
132            let linestart = y * self.width;
133            let dy = ((y + 1) as f32).min(p1.y) - (y as f32).max(p0.y);
134            let xnext = x + dxdy * dy;
135            let d = dy * dir;
136            let (x0, x1) = if x < xnext { (x, xnext) } else { (xnext, x) };
137            let x0floor = x0.floor();
138            let x0i = x0floor as i32;
139            let x1ceil = x1.ceil();
140            let x1i = x1ceil as i32;
141            let linestart_x0i = linestart as isize + x0i as isize;
142            if linestart_x0i < 0 {
143                continue;
144            }
145            if x1i <= x0i + 1 {
146                let xmf = 0.5 * (x + xnext) - x0floor;
147                add_assign_a_idx!(linestart_x0i as usize, d - d * xmf);
148                add_assign_a_idx!(linestart_x0i as usize + 1, d * xmf);
149            } else {
150                let s = (x1 - x0).recip();
151                let x0f = x0 - x0floor;
152                let a0 = 0.5 * s * (1.0 - x0f) * (1.0 - x0f);
153                let x1f = x1 - x1ceil + 1.0;
154                let am = 0.5 * s * x1f * x1f;
155                add_assign_a_idx!(linestart_x0i as usize, d * a0);
156                if x1i == x0i + 2 {
157                    add_assign_a_idx!(linestart_x0i as usize + 1, d * (1.0 - a0 - am));
158                } else {
159                    let a1 = s * (1.5 - x0f);
160                    add_assign_a_idx!(linestart_x0i as usize + 1, d * (a1 - a0));
161                    for xi in x0i + 2..x1i - 1 {
162                        add_assign_a_idx!(linestart + xi as usize, d * s);
163                    }
164                    let a2 = a1 + (x1i - x0i - 3) as f32 * s;
165                    add_assign_a_idx!(linestart + (x1i - 1) as usize, d * (1.0 - a2 - am));
166                }
167                add_assign_a_idx!(linestart + x1i as usize, d * am);
168            }
169            x = xnext;
170        }
171    }
172
173    /// Adds a quadratic Bézier curve from `p0` to `p2` to the outline using `p1` as the control.
174    ///
175    /// ```
176    /// # use ab_glyph_rasterizer::*;
177    /// # let mut rasterizer = Rasterizer::new(14, 38);
178    /// rasterizer.draw_quad(point(6.2, 34.5), point(7.2, 34.5), point(9.2, 34.0));
179    /// ```
180    pub fn draw_quad(&mut self, p0: Point, p1: Point, p2: Point) {
181        let devx = p0.x - 2.0 * p1.x + p2.x;
182        let devy = p0.y - 2.0 * p1.y + p2.y;
183        let devsq = devx * devx + devy * devy;
184        if devsq < 0.333 {
185            self.draw_line(p0, p2);
186            return;
187        }
188        let tol = 3.0;
189        let n = 1 + (tol * devsq).sqrt().sqrt().floor() as usize;
190        let mut p = p0;
191        let nrecip = (n as f32).recip();
192        let mut t = 0.0;
193        for _i in 0..n - 1 {
194            t += nrecip;
195            let pn = lerp(t, lerp(t, p0, p1), lerp(t, p1, p2));
196            self.draw_line(p, pn);
197            p = pn;
198        }
199        self.draw_line(p, p2);
200    }
201
202    /// Adds a cubic Bézier curve from `p0` to `p3` to the outline using `p1` as the control
203    /// at the beginning of the curve and `p2` at the end of the curve.
204    ///
205    /// ```
206    /// # use ab_glyph_rasterizer::*;
207    /// # let mut rasterizer = Rasterizer::new(12, 20);
208    /// rasterizer.draw_cubic(
209    ///     point(10.3, 16.4),
210    ///     point(8.6, 16.9),
211    ///     point(7.7, 16.5),
212    ///     point(8.2, 15.2),
213    /// );
214    /// ```
215    pub fn draw_cubic(&mut self, p0: Point, p1: Point, p2: Point, p3: Point) {
216        self.tessellate_cubic(p0, p1, p2, p3, 0);
217    }
218
219    // stb_truetype style cubic approximation by lines.
220    fn tessellate_cubic(&mut self, p0: Point, p1: Point, p2: Point, p3: Point, n: u8) {
221        // ...I'm not sure either ¯\_(ツ)_/¯
222        const OBJSPACE_FLATNESS: f32 = 0.35;
223        const OBJSPACE_FLATNESS_SQUARED: f32 = OBJSPACE_FLATNESS * OBJSPACE_FLATNESS;
224        const MAX_RECURSION_DEPTH: u8 = 16;
225
226        let longlen = p0.distance_to(p1) + p1.distance_to(p2) + p2.distance_to(p3);
227        let shortlen = p0.distance_to(p3);
228        let flatness_squared = longlen * longlen - shortlen * shortlen;
229
230        if n < MAX_RECURSION_DEPTH && flatness_squared > OBJSPACE_FLATNESS_SQUARED {
231            let p01 = lerp(0.5, p0, p1);
232            let p12 = lerp(0.5, p1, p2);
233            let p23 = lerp(0.5, p2, p3);
234
235            let pa = lerp(0.5, p01, p12);
236            let pb = lerp(0.5, p12, p23);
237
238            let mp = lerp(0.5, pa, pb);
239
240            self.tessellate_cubic(p0, p01, pa, mp, n + 1);
241            self.tessellate_cubic(mp, pb, p23, p3, n + 1);
242        } else {
243            self.draw_line(p0, p3);
244        }
245    }
246
247    /// Run a callback for each pixel `index` & `alpha`, with indices in `0..width * height`.
248    ///
249    /// An `alpha` coverage value of `0.0` means the pixel is not covered at all by the glyph,
250    /// whereas a value of `1.0` (or greater) means the pixel is totally covered.
251    ///
252    /// ```
253    /// # use ab_glyph_rasterizer::*;
254    /// # let (width, height) = (1, 1);
255    /// # let mut rasterizer = Rasterizer::new(width, height);
256    /// let mut pixels = vec![0u8; width * height];
257    /// rasterizer.for_each_pixel(|index, alpha| {
258    ///     pixels[index] = (alpha * 255.0) as u8;
259    /// });
260    /// ```
261    pub fn for_each_pixel<O: FnMut(usize, f32)>(&self, mut px_fn: O) {
262        let mut acc = 0.0;
263        self.a[..self.width * self.height]
264            .iter()
265            .enumerate()
266            .for_each(|(idx, c)| {
267                acc += c;
268                px_fn(idx, acc.abs());
269            });
270    }
271
272    /// Run a callback for each pixel x position, y position & alpha.
273    ///
274    /// Convenience wrapper for [`Rasterizer::for_each_pixel`].
275    ///
276    /// ```
277    /// # use ab_glyph_rasterizer::*;
278    /// # let mut rasterizer = Rasterizer::new(1, 1);
279    /// # struct Img;
280    /// # impl Img { fn set_pixel(&self, x: u32, y: u32, a: u8) {} }
281    /// # let image = Img;
282    /// rasterizer.for_each_pixel_2d(|x, y, alpha| {
283    ///     image.set_pixel(x, y, (alpha * 255.0) as u8);
284    /// });
285    /// ```
286    pub fn for_each_pixel_2d<O: FnMut(u32, u32, f32)>(&self, mut px_fn: O) {
287        let width32 = self.width as u32;
288        self.for_each_pixel(|idx, alpha| px_fn(idx as u32 % width32, idx as u32 / width32, alpha));
289    }
290}
291
292/// ```
293/// let rasterizer = ab_glyph_rasterizer::Rasterizer::new(3, 4);
294/// assert_eq!(
295///     &format!("{:?}", rasterizer),
296///     "Rasterizer { width: 3, height: 4 }"
297/// );
298/// ```
299impl core::fmt::Debug for Rasterizer {
300    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
301        f.debug_struct("Rasterizer")
302            .field("width", &self.width)
303            .field("height", &self.height)
304            .finish()
305    }
306}
307
308#[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
309#[target_feature(enable = "avx2")]
310unsafe fn draw_line_avx2(rast: &mut Rasterizer, p0: Point, p1: Point) {
311    rast.draw_line_scalar(p0, p1)
312}
313
314#[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
315#[target_feature(enable = "sse4.2")]
316unsafe fn draw_line_sse4_2(rast: &mut Rasterizer, p0: Point, p1: Point) {
317    rast.draw_line_scalar(p0, p1)
318}
319
320/// Return most optimal `DrawLineFn` impl.
321///
322/// With feature `std` on x86/x86_64 will use one-time runtime detection
323/// to pick the best SIMD impl. Otherwise uses a scalar version.
324fn optimal_draw_line_fn() -> DrawLineFn {
325    unsafe {
326        // safe as write synchronised by Once::call_once or no-write
327        static mut DRAW_LINE_FN: DrawLineFn = Rasterizer::draw_line_scalar;
328
329        #[cfg(all(feature = "std", any(target_arch = "x86", target_arch = "x86_64")))]
330        {
331            static INIT: std::sync::Once = std::sync::Once::new();
332            INIT.call_once(|| {
333                // runtime detect optimal simd impls
334                if is_x86_feature_detected!("avx2") {
335                    DRAW_LINE_FN = draw_line_avx2
336                } else if is_x86_feature_detected!("sse4.2") {
337                    DRAW_LINE_FN = draw_line_sse4_2
338                }
339            });
340        }
341
342        DRAW_LINE_FN
343    }
344}
ab_glyph_rasterizer/raster.rs

ab_glyph_rasterizer/
raster.rs
