gpu_cache.rs 40.1 KB
Newer Older
Jim Blandy's avatar
Jim Blandy committed
1 2 3
//! This module provides capabilities for managing a cache of rendered glyphs in
//! GPU memory, with the goal of minimisng the size and frequency of glyph
//! uploads to GPU memory from the CPU.
4
//!
Jim Blandy's avatar
Jim Blandy committed
5 6
//! This module is optional, and not compiled by default. To use it enable the
//! `gpu_cache` feature in your Cargo.toml.
7
//!
Jim Blandy's avatar
Jim Blandy committed
8 9 10 11 12 13 14 15
//! Typical applications that render directly with hardware graphics APIs (e.g.
//! games) need text rendering. There is not yet a performant solution for high
//! quality text rendering directly on the GPU that isn't experimental research
//! work. Quality is often critical for legibility, so many applications use
//! text or individual characters that have been rendered on the CPU. This is
//! done either ahead-of-time, giving a fixed set of fonts, characters, and
//! sizes that can be used at runtime, or dynamically as text is required. This
//! latter scenario is more flexible and the focus of this module.
Alex Butler's avatar
Alex Butler committed
16
//!
Jim Blandy's avatar
Jim Blandy committed
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
//! To minimise the CPU load and texture upload bandwidth saturation, recently
//! used glyphs should be cached on the GPU for use by future frames. This
//! module provides a mechanism for maintaining such a cache in the form of a
//! single packed 2D GPU texture. When a rendered glyph is requested, it is
//! either retrieved from its location in the texture if it is present or room
//! is made in the cache (if necessary), the CPU renders the glyph then it is
//! uploaded into a gap in the texture to be available for GPU rendering. This
//! cache uses a Least Recently Used (LRU) cache eviction scheme - glyphs in the
//! cache that have not been used recently are as a rule of thumb not likely to
//! be used again soon, so they are the best candidates for eviction to make
//! room for required glyphs.
//!
//! The API for the cache does not assume a particular graphics API. The
//! intended usage is to queue up glyphs that need to be present for the current
//! frame using `Cache::queue_glyph`, update the cache to ensure that the queued
//! glyphs are present using `Cache::cache_queued` (providing a function for
//! uploading pixel data), then when it's time to render call `Cache::rect_for`
//! to get the UV coordinates in the cache texture for each glyph. For a
//! concrete use case see the `gpu_cache` example.
Alex Butler's avatar
Alex Butler committed
36
//!
37
//! Cache dimensions are immutable. If you need to change the dimensions of the
38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
//! cache texture (e.g. due to high cache pressure), rebuild a new `Cache`.
//! Either from scratch or with `CacheBuilder::rebuild`.
//!
//! # Example
//!
//! ```
//! # use rusttype::{Font, gpu_cache::Cache, point, Scale};
//! # use std::error::Error;
//! # fn example() -> Result<(), Box<Error>> {
//! # let font_data: &[u8] = include_bytes!("../fonts/dejavu/DejaVuSansMono.ttf");
//! # let font: Font<'static> = Font::from_bytes(font_data)?;
//! # let glyph = font.glyph('a').scaled(Scale::uniform(25.0)).positioned(point(0.0, 0.0));
//! # let glyph2 = glyph.clone();
//! # let update_gpu_texture = |_, _| {};
//! // Build a default Cache.
//! let mut cache = Cache::builder().build();
//!
//! // Queue some positioned glyphs needed for the next frame.
//! cache.queue_glyph(0, glyph);
//!
//! // Cache all queued glyphs somewhere in the cache texture.
//! // If new glyph data has been drawn the closure is called to upload
//! // the pixel data to GPU memory.
//! cache.cache_queued(|region, data| update_gpu_texture(region, data))?;
//!
//! # let glyph = glyph2;
//! // Lookup a positioned glyph's texture location
//! if let Ok(Some((uv_rect, screen_rect))) = cache.rect_for(0, &glyph) {
//!     // Generate vertex data, etc
//! }
//! # Ok(())
//! # }
//! ```
Alex Butler's avatar
Alex Butler committed
71 72
use linked_hash_map::LinkedHashMap;
use rustc_hash::{FxHashMap, FxHasher};
73
use std::collections::{HashMap, HashSet};
74 75
use std::error;
use std::fmt;
76
use std::hash::BuildHasherDefault;
Alex Butler's avatar
Alex Butler committed
77
use crate::{point, vector, GlyphId, Point, PositionedGlyph, Rect, Vector};
78

79 80
type FxBuildHasher = BuildHasherDefault<FxHasher>;

Alex Butler's avatar
Alex Butler committed
81 82 83 84
/// Texture coordinates (floating point) of the quad for a glyph in the cache,
/// as well as the pixel-space (integer) coordinates that this region should be
/// drawn at.
pub type TextureCoords = (Rect<f32>, Rect<i32>);
85 86
type FontId = usize;

Alex Butler's avatar
Alex Butler committed
87 88 89 90
/// Indicates where a glyph texture is stored in the cache
/// (row position, glyph index in row)
type TextureRowGlyphIndex = (u32, u32);

91 92 93 94 95 96
/// Texture lookup key that uses scale & offset as integers attained
/// by dividing by the relevant tolerance.
#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
struct LossyGlyphInfo {
    font_id: FontId,
    glyph_id: GlyphId,
97
    /// x & y scales divided by `scale_tolerance` & rounded
98
    scale_over_tolerance: (u32, u32),
99
    /// Normalised subpixel positions divided by `position_tolerance` & rounded
100
    ///
101 102
    /// `u16` is enough as subpixel position `[-0.5, 0.5]` converted to `[0, 1]`
    ///  divided by the min `position_tolerance` (`0.001`) is small.
103
    offset_over_tolerance: (u16, u16),
104 105
}

106 107 108 109 110 111 112 113
#[derive(Debug, Clone, PartialEq, Eq)]
struct ByteArray2d {
    inner_array: Vec<u8>,
    row: usize,
    col: usize,
}

impl ByteArray2d {
114
    #[inline]
115 116 117
    pub fn zeros(row: usize, col: usize) -> Self {
        ByteArray2d {
            inner_array: vec![0; row * col],
Jim Blandy's avatar
Jim Blandy committed
118 119
            row,
            col,
120 121 122
        }
    }

123 124
    #[inline]
    fn as_slice(&self) -> &[u8] {
125 126 127
        self.inner_array.as_slice()
    }

128
    #[inline]
129
    fn get_vec_index(&self, row: usize, col: usize) -> usize {
130 131 132 133 134 135 136 137 138 139 140 141 142
        debug_assert!(
            row < self.row,
            "row out of range: row={}, given={}",
            self.row,
            row
        );
        debug_assert!(
            col < self.col,
            "column out of range: col={}, given={}",
            self.col,
            col
        );
        row * self.col + col
143 144 145
    }
}

Alex Butler's avatar
Alex Butler committed
146
impl std::ops::Index<(usize, usize)> for ByteArray2d {
147 148
    type Output = u8;

149
    #[inline]
150 151 152 153 154
    fn index(&self, (row, col): (usize, usize)) -> &u8 {
        &self.inner_array[self.get_vec_index(row, col)]
    }
}

Alex Butler's avatar
Alex Butler committed
155
impl std::ops::IndexMut<(usize, usize)> for ByteArray2d {
156
    #[inline]
157 158 159 160 161 162
    fn index_mut(&mut self, (row, col): (usize, usize)) -> &mut u8 {
        let vec_index = self.get_vec_index(row, col);
        &mut self.inner_array[vec_index]
    }
}

Alex Butler's avatar
Alex Butler committed
163
/// Row of pixel data
164
struct Row {
Alex Butler's avatar
Alex Butler committed
165
    /// Row pixel height
166
    height: u32,
Alex Butler's avatar
Alex Butler committed
167
    /// Pixel width current in use by glyphs
168
    width: u32,
Alex Butler's avatar
Alex Butler committed
169 170 171 172
    glyphs: Vec<GlyphTexInfo>,
}

struct GlyphTexInfo {
173 174 175
    glyph_info: LossyGlyphInfo,
    /// Actual (lossless) normalised subpixel offset of rasterized glyph
    offset: Vector<f32>,
Alex Butler's avatar
Alex Butler committed
176
    tex_coords: Rect<u32>,
177 178
}

Alex Butler's avatar
Alex Butler committed
179 180 181 182 183
trait PaddingAware {
    fn unpadded(self) -> Self;
}

impl PaddingAware for Rect<u32> {
184
    /// A padded texture has 1 extra pixel on all sides
Alex Butler's avatar
Alex Butler committed
185
    fn unpadded(mut self) -> Self {
186 187
        self.min.x += 1;
        self.min.y += 1;
Alex Butler's avatar
Alex Butler committed
188 189 190 191 192 193
        self.max.x -= 1;
        self.max.y -= 1;
        self
    }
}

Jim Blandy's avatar
Jim Blandy committed
194 195
/// An implementation of a dynamic GPU glyph cache. See the module documentation
/// for more information.
196
pub struct Cache<'font> {
197 198 199 200
    scale_tolerance: f32,
    position_tolerance: f32,
    width: u32,
    height: u32,
201
    rows: LinkedHashMap<u32, Row, FxBuildHasher>,
Alex Butler's avatar
Alex Butler committed
202
    /// Mapping of row gaps bottom -> top
203
    space_start_for_end: FxHashMap<u32, u32>,
Alex Butler's avatar
Alex Butler committed
204
    /// Mapping of row gaps top -> bottom
205
    space_end_for_start: FxHashMap<u32, u32>,
206
    queue: Vec<(FontId, PositionedGlyph<'font>)>,
207
    all_glyphs: FxHashMap<LossyGlyphInfo, TextureRowGlyphIndex>,
208
    pad_glyphs: bool,
209
    multithread: bool,
210 211
}

212
/// Builder & rebuilder for `Cache`.
213 214 215 216
///
/// # Example
///
/// ```
217
/// use rusttype::gpu_cache::Cache;
218
///
219 220
/// // Create a cache with all default values set explicitly
/// // equivalent to `Cache::builder().build()`
221 222 223 224 225 226 227
/// let default_cache = Cache::builder()
///     .dimensions(256, 256)
///     .scale_tolerance(0.1)
///     .position_tolerance(0.1)
///     .pad_glyphs(true)
///     .multithread(true)
///     .build();
228
///
229
/// // Create a cache with all default values, except with a dimension of 1024x1024
230
/// let bigger_cache = Cache::builder().dimensions(1024, 1024).build();
231 232 233
/// ```
#[derive(Debug, Clone)]
pub struct CacheBuilder {
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
    dimensions: (u32, u32),
    scale_tolerance: f32,
    position_tolerance: f32,
    pad_glyphs: bool,
    multithread: bool,
}

impl Default for CacheBuilder {
    fn default() -> Self {
        Self {
            dimensions: (256, 256),
            scale_tolerance: 0.1,
            position_tolerance: 0.1,
            pad_glyphs: true,
            multithread: true,
        }
    }
}

impl CacheBuilder {
    /// `width` & `height` dimensions of the 2D texture that will hold the
    /// cache contents on the GPU.
256 257 258 259 260
    ///
    /// This must match the dimensions of the actual texture used, otherwise
    /// `cache_queued` will try to cache into coordinates outside the bounds of
    /// the texture.
    ///
261
    /// # Example (set to default value)
262 263 264
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
265
    /// let cache = Cache::builder().dimensions(256, 256).build();
266 267 268 269 270 271
    /// ```
    pub fn dimensions(mut self, width: u32, height: u32) -> Self {
        self.dimensions = (width, height);
        self
    }

272 273 274
    /// Specifies the tolerances (maximum allowed difference) for judging
    /// whether an existing glyph in the cache is close enough to the
    /// requested glyph in scale to be used in its place. Due to floating
275
    /// point inaccuracies a min value of `0.001` is enforced.
276 277 278
    ///
    /// Both `scale_tolerance` and `position_tolerance` are measured in pixels.
    ///
279 280 281 282 283
    /// Tolerances produce even steps for scale and subpixel position. Only a
    /// single glyph texture will be used within a single step. For example,
    /// `scale_tolerance = 0.1` will have a step `9.95-10.05` so similar glyphs
    /// with scale `9.98` & `10.04` will match.
    ///
284 285 286
    /// A typical application will produce results with no perceptible
    /// inaccuracies with `scale_tolerance` and `position_tolerance` set to
    /// 0.1. Depending on the target DPI higher tolerance may be acceptable.
287
    ///
288
    /// # Example (set to default value)
289 290 291
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
292
    /// let cache = Cache::builder().scale_tolerance(0.1).build();
293 294 295 296 297
    /// ```
    pub fn scale_tolerance<V: Into<f32>>(mut self, scale_tolerance: V) -> Self {
        self.scale_tolerance = scale_tolerance.into();
        self
    }
298 299
    /// Specifies the tolerances (maximum allowed difference) for judging
    /// whether an existing glyph in the cache is close enough to the requested
300 301
    /// glyph in subpixel offset to be used in its place. Due to floating
    /// point inaccuracies a min value of `0.001` is enforced.
302 303 304
    ///
    /// Both `scale_tolerance` and `position_tolerance` are measured in pixels.
    ///
305 306 307 308 309
    /// Tolerances produce even steps for scale and subpixel position. Only a
    /// single glyph texture will be used within a single step. For example,
    /// `scale_tolerance = 0.1` will have a step `9.95-10.05` so similar glyphs
    /// with scale `9.98` & `10.04` will match.
    ///
310 311 312 313 314 315 316
    /// Note that since `position_tolerance` is a tolerance of subpixel
    /// offsets, setting it to 1.0 or higher is effectively a "don't care"
    /// option.
    ///
    /// A typical application will produce results with no perceptible
    /// inaccuracies with `scale_tolerance` and `position_tolerance` set to
    /// 0.1. Depending on the target DPI higher tolerance may be acceptable.
317
    ///
318
    /// # Example (set to default value)
319 320 321
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
322
    /// let cache = Cache::builder().position_tolerance(0.1).build();
323 324 325 326 327
    /// ```
    pub fn position_tolerance<V: Into<f32>>(mut self, position_tolerance: V) -> Self {
        self.position_tolerance = position_tolerance.into();
        self
    }
328 329 330 331 332
    /// Pack glyphs in texture with a padding of a single zero alpha pixel to
    /// avoid bleeding from interpolated shader texture lookups near edges.
    ///
    /// If glyphs are never transformed this may be set to `false` to slightly
    /// improve the glyph packing.
333
    ///
334
    /// # Example (set to default value)
335 336 337
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
338
    /// let cache = Cache::builder().pad_glyphs(true).build();
339 340 341 342 343
    /// ```
    pub fn pad_glyphs(mut self, pad_glyphs: bool) -> Self {
        self.pad_glyphs = pad_glyphs;
        self
    }
344 345 346 347
    /// When multiple CPU cores are available spread rasterization work across
    /// all cores.
    ///
    /// Significantly reduces worst case latency in multicore environments.
348
    ///
349
    /// # Example (set to default value)
350 351 352
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
353
    /// let cache = Cache::builder().multithread(true).build();
354 355 356 357
    /// ```
    pub fn multithread(mut self, multithread: bool) -> Self {
        self.multithread = multithread;
        self
358 359
    }

360 361 362 363 364
    fn validated(self) -> Self {
        assert!(self.scale_tolerance >= 0.0);
        assert!(self.position_tolerance >= 0.0);
        let scale_tolerance = self.scale_tolerance.max(0.001);
        let position_tolerance = self.position_tolerance.max(0.001);
365
        let multithread = self.multithread && num_cpus::get() > 1;
366 367 368
        Self {
            scale_tolerance,
            position_tolerance,
369
            multithread,
370 371 372 373
            ..self
        }
    }

374 375 376 377 378 379 380
    /// Constructs a new cache. Note that this is just the CPU side of the
    /// cache. The GPU texture is managed by the user.
    ///
    /// # Panics
    ///
    /// `scale_tolerance` or `position_tolerance` are less than or equal to
    /// zero.
381 382 383 384 385 386 387
    ///
    /// # Example
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
    /// let cache = Cache::builder().build();
    /// ```
388 389
    pub fn build<'a>(self) -> Cache<'a> {
        let CacheBuilder {
390
            dimensions: (width, height),
391 392 393
            scale_tolerance,
            position_tolerance,
            pad_glyphs,
394
            multithread,
395
        } = self.validated();
396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415

        Cache {
            scale_tolerance,
            position_tolerance,
            width,
            height,
            rows: LinkedHashMap::default(),
            space_start_for_end: {
                let mut m = HashMap::default();
                m.insert(height, 0);
                m
            },
            space_end_for_start: {
                let mut m = HashMap::default();
                m.insert(0, height);
                m
            },
            queue: Vec::new(),
            all_glyphs: HashMap::default(),
            pad_glyphs,
416
            multithread,
417 418
        }
    }
419 420 421 422 423 424 425 426

    /// Rebuilds a cache with new attributes. Carries over the existing cache
    /// queue unmodified.
    ///
    /// # Panics
    ///
    /// `scale_tolerance` or `position_tolerance` are less than or equal to
    /// zero.
427 428 429 430 431 432 433 434 435
    ///
    /// # Example
    ///
    /// ```
    /// # use rusttype::gpu_cache::Cache;
    /// # let mut cache = Cache::builder().build();
    /// // Rebuild the cache with different dimensions
    /// cache.to_builder().dimensions(768, 768).rebuild(&mut cache);
    /// ```
436 437
    pub fn rebuild(self, cache: &mut Cache) {
        let CacheBuilder {
438
            dimensions: (width, height),
439 440 441
            scale_tolerance,
            position_tolerance,
            pad_glyphs,
442
            multithread,
443 444 445 446 447 448 449
        } = self.validated();

        cache.width = width;
        cache.height = height;
        cache.scale_tolerance = scale_tolerance;
        cache.position_tolerance = position_tolerance;
        cache.pad_glyphs = pad_glyphs;
450
        cache.multithread = multithread;
451 452
        cache.clear();
    }
453 454
}

455
/// Returned from `Cache::rect_for`.
456 457
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum CacheReadErr {
458
    /// Indicates that the requested glyph is not present in the cache
Jim Blandy's avatar
Jim Blandy committed
459
    GlyphNotCached,
460
}
461 462 463 464 465 466 467 468 469 470 471 472 473
impl fmt::Display for CacheReadErr {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", error::Error::description(self))
    }
}
impl error::Error for CacheReadErr {
    fn description(&self) -> &str {
        match *self {
            CacheReadErr::GlyphNotCached => "Glyph not cached",
        }
    }
}

474
/// Returned from `Cache::cache_queued`.
475 476
#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum CacheWriteErr {
Jim Blandy's avatar
Jim Blandy committed
477 478
    /// At least one of the queued glyphs is too big to fit into the cache, even
    /// if all other glyphs are removed.
479
    GlyphTooLarge,
Jim Blandy's avatar
Jim Blandy committed
480 481 482
    /// Not all of the requested glyphs can fit into the cache, even if the
    /// cache is completely cleared before the attempt.
    NoRoomForWholeQueue,
483
}
484 485 486 487 488 489 490 491 492 493 494 495 496 497
impl fmt::Display for CacheWriteErr {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", error::Error::description(self))
    }
}
impl error::Error for CacheWriteErr {
    fn description(&self) -> &str {
        match *self {
            CacheWriteErr::GlyphTooLarge => "Glyph too large",
            CacheWriteErr::NoRoomForWholeQueue => "No room for whole queue",
        }
    }
}

498 499
fn normalised_offset_from_position(position: Point<f32>) -> Vector<f32> {
    let mut offset = vector(position.x.fract(), position.y.fract());
500 501 502 503 504 505 506 507 508 509 510 511
    if offset.x > 0.5 {
        offset.x -= 1.0;
    } else if offset.x < -0.5 {
        offset.x += 1.0;
    }
    if offset.y > 0.5 {
        offset.y -= 1.0;
    } else if offset.y < -0.5 {
        offset.y += 1.0;
    }
    offset
}
512

513
impl<'font> Cache<'font> {
514 515 516 517
    /// Returns a default `CacheBuilder`.
    #[inline]
    pub fn builder() -> CacheBuilder {
        CacheBuilder::default()
518
    }
519

520 521 522 523
    /// Returns the current scale tolerance for the cache.
    pub fn scale_tolerance(&self) -> f32 {
        self.scale_tolerance
    }
524

525 526 527 528
    /// Returns the current subpixel position tolerance for the cache.
    pub fn position_tolerance(&self) -> f32 {
        self.position_tolerance
    }
529

Jim Blandy's avatar
Jim Blandy committed
530 531
    /// Returns the cache texture dimensions assumed by the cache. For proper
    /// operation this should match the dimensions of the used GPU texture.
532 533 534
    pub fn dimensions(&self) -> (u32, u32) {
        (self.width, self.height)
    }
535

Jim Blandy's avatar
Jim Blandy committed
536 537 538
    /// Queue a glyph for caching by the next call to `cache_queued`. `font_id`
    /// is used to disambiguate glyphs from different fonts. The user should
    /// ensure that `font_id` is unique to the font the glyph is from.
539
    pub fn queue_glyph(&mut self, font_id: usize, glyph: PositionedGlyph<'font>) {
540
        if glyph.pixel_bounding_box().is_some() {
541
            self.queue.push((font_id, glyph));
542 543
        }
    }
544

545 546 547 548 549 550 551 552 553
    /// Clears the cache. Does not affect the glyph queue.
    pub fn clear(&mut self) {
        self.rows.clear();
        self.space_end_for_start.clear();
        self.space_end_for_start.insert(0, self.height);
        self.space_start_for_end.clear();
        self.space_start_for_end.insert(self.height, 0);
        self.all_glyphs.clear();
    }
554

555 556 557 558
    /// Clears the glyph queue.
    pub fn clear_queue(&mut self) {
        self.queue.clear();
    }
559

560 561 562
    /// Returns a `CacheBuilder` with this cache's attributes.
    pub fn to_builder(&self) -> CacheBuilder {
        CacheBuilder {
563
            dimensions: (self.width, self.height),
564 565 566
            position_tolerance: self.position_tolerance,
            scale_tolerance: self.scale_tolerance,
            pad_glyphs: self.pad_glyphs,
567
            multithread: self.multithread,
568 569 570 571
        }
    }

    /// Returns glyph info with accuracy according to the set tolerances.
572 573 574 575 576 577 578 579
    fn lossy_info_for(&self, font_id: FontId, glyph: &PositionedGlyph<'font>) -> LossyGlyphInfo {
        let scale = glyph.scale();
        let offset = normalised_offset_from_position(glyph.position());

        LossyGlyphInfo {
            font_id,
            glyph_id: glyph.id(),
            scale_over_tolerance: (
580 581
                (scale.x / self.scale_tolerance + 0.5) as u32,
                (scale.y / self.scale_tolerance + 0.5) as u32,
582
            ),
583
            // convert [-0.5, 0.5] -> [0, 1] then divide
584
            offset_over_tolerance: (
585 586
                ((offset.x + 0.5) / self.position_tolerance + 0.5) as u16,
                ((offset.y + 0.5) / self.position_tolerance + 0.5) as u16,
587 588 589 590
            ),
        }
    }

Jim Blandy's avatar
Jim Blandy committed
591 592 593 594 595
    /// Caches the queued glyphs. If this is unsuccessful, the queue is
    /// untouched. Any glyphs cached by previous calls to this function may be
    /// removed from the cache to make room for the newly queued glyphs. Thus if
    /// you want to ensure that a glyph is in the cache, the most recently
    /// cached queue must have contained that glyph.
596
    ///
Jim Blandy's avatar
Jim Blandy committed
597 598 599 600 601
    /// `uploader` is the user-provided function that should perform the texture
    /// uploads to the GPU. The information provided is the rectangular region
    /// to insert the pixel data into, and the pixel data itself. This data is
    /// provided in horizontal scanline format (row major), with stride equal to
    /// the rectangle width.
602 603 604 605
    pub fn cache_queued<F: FnMut(Rect<u32>, &[u8])>(
        &mut self,
        mut uploader: F,
    ) -> Result<(), CacheWriteErr> {
606
        let mut queue_success = true;
607
        let from_empty = self.all_glyphs.is_empty();
608

Alex Butler's avatar
Alex Butler committed
609
        {
610 611
            let (mut in_use_rows, mut uncached_glyphs) = {
                let mut in_use_rows =
612
                    HashSet::with_capacity_and_hasher(self.rows.len(), FxBuildHasher::default());
613 614 615 616 617 618 619 620 621 622 623 624 625 626 627
                let mut uncached_glyphs = Vec::with_capacity(self.queue.len());

                // divide glyphs into texture rows where a matching glyph texture
                // already exists & glyphs where new textures must be cached
                for (font_id, ref glyph) in &self.queue {
                    let glyph_info = self.lossy_info_for(*font_id, glyph);
                    if let Some((row, ..)) = self.all_glyphs.get(&glyph_info) {
                        in_use_rows.insert(*row);
                    } else {
                        uncached_glyphs.push((glyph, glyph_info));
                    }
                }

                (in_use_rows, uncached_glyphs)
            };
Alex Butler's avatar
Alex Butler committed
628 629 630

            for row in &in_use_rows {
                self.rows.get_refresh(row);
631
            }
Alex Butler's avatar
Alex Butler committed
632 633 634

            // tallest first gives better packing
            // can use 'sort_unstable' as order of equal elements is unimportant
635 636
            uncached_glyphs
                .sort_unstable_by_key(|(glyph, ..)| -glyph.pixel_bounding_box().unwrap().height());
Alex Butler's avatar
Alex Butler committed
637

638
            self.all_glyphs.reserve(uncached_glyphs.len());
639
            let mut draw_and_upload = Vec::with_capacity(uncached_glyphs.len());
640 641 642 643

            'per_glyph: for (glyph, glyph_info) in uncached_glyphs {
                // glyph may match a texture cached by a previous iteration
                if self.all_glyphs.contains_key(&glyph_info) {
Alex Butler's avatar
Alex Butler committed
644
                    continue;
645 646
                }

Alex Butler's avatar
Alex Butler committed
647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664
                // Not cached, so add it:
                let (width, height) = {
                    let bb = glyph.pixel_bounding_box().unwrap();
                    if self.pad_glyphs {
                        (bb.width() as u32 + 2, bb.height() as u32 + 2)
                    } else {
                        (bb.width() as u32, bb.height() as u32)
                    }
                };
                if width >= self.width || height >= self.height {
                    return Result::Err(CacheWriteErr::GlyphTooLarge);
                }
                // find row to put the glyph in, most used rows first
                let mut row_top = None;
                for (top, row) in self.rows.iter().rev() {
                    if row.height >= height && self.width - row.width >= width {
                        // found a spot on an existing row
                        row_top = Some(*top);
665 666 667
                        break;
                    }
                }
Alex Butler's avatar
Alex Butler committed
668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686

                if row_top.is_none() {
                    let mut gap = None;
                    // See if there is space for a new row
                    for (start, end) in &self.space_end_for_start {
                        if end - start >= height {
                            gap = Some((*start, *end));
                            break;
                        }
                    }
                    if gap.is_none() {
                        // Remove old rows until room is available
                        while !self.rows.is_empty() {
                            // check that the oldest row isn't also in use
                            if !in_use_rows.contains(self.rows.front().unwrap().0) {
                                // Remove row
                                let (top, row) = self.rows.pop_front().unwrap();

                                for g in row.glyphs {
687
                                    self.all_glyphs.remove(&g.glyph_info);
688
                                }
Alex Butler's avatar
Alex Butler committed
689

Alex Butler's avatar
Alex Butler committed
690 691
                                let (mut new_start, mut new_end) = (top, top + row.height);
                                // Update the free space maps
692
                                // Combine with neighbouring free space if possible
Alex Butler's avatar
Alex Butler committed
693 694 695 696 697 698 699 700 701 702 703 704 705
                                if let Some(end) = self.space_end_for_start.remove(&new_end) {
                                    new_end = end;
                                }
                                if let Some(start) = self.space_start_for_end.remove(&new_start) {
                                    new_start = start;
                                }
                                self.space_start_for_end.insert(new_end, new_start);
                                self.space_end_for_start.insert(new_start, new_end);
                                if new_end - new_start >= height {
                                    // The newly formed gap is big enough
                                    gap = Some((new_start, new_end));
                                    break;
                                }
706
                            }
Alex Butler's avatar
Alex Butler committed
707 708 709
                            // all rows left are in use
                            // try a clean insert of all needed glyphs
                            // if that doesn't work, fail
710
                            else if from_empty {
Alex Butler's avatar
Alex Butler committed
711 712 713 714 715 716
                                // already trying a clean insert, don't do it again
                                return Err(CacheWriteErr::NoRoomForWholeQueue);
                            } else {
                                // signal that a retry is needed
                                queue_success = false;
                                break 'per_glyph;
717
                            }
718
                        }
719
                    }
Alex Butler's avatar
Alex Butler committed
720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739
                    let (gap_start, gap_end) = gap.unwrap();
                    // fill space for new row
                    let new_space_start = gap_start + height;
                    self.space_end_for_start.remove(&gap_start);
                    if new_space_start == gap_end {
                        self.space_start_for_end.remove(&gap_end);
                    } else {
                        self.space_end_for_start.insert(new_space_start, gap_end);
                        self.space_start_for_end.insert(gap_end, new_space_start);
                    }
                    // add the row
                    self.rows.insert(
                        gap_start,
                        Row {
                            width: 0,
                            height,
                            glyphs: Vec::new(),
                        },
                    );
                    row_top = Some(gap_start);
740
                }
Alex Butler's avatar
Alex Butler committed
741 742 743
                let row_top = row_top.unwrap();
                // calculate the target rect
                let row = self.rows.get_refresh(&row_top).unwrap();
744
                let tex_coords = Rect {
Alex Butler's avatar
Alex Butler committed
745 746 747
                    min: point(row.width, row_top),
                    max: point(row.width + width, row_top + height),
                };
748 749 750

                draw_and_upload.push((tex_coords, glyph));

Alex Butler's avatar
Alex Butler committed
751 752
                // add the glyph to the row
                row.glyphs.push(GlyphTexInfo {
753 754
                    glyph_info,
                    offset: normalised_offset_from_position(glyph.position()),
755
                    tex_coords,
756
                });
Alex Butler's avatar
Alex Butler committed
757 758 759 760
                row.width += width;
                in_use_rows.insert(row_top);

                self.all_glyphs
761
                    .insert(glyph_info, (row_top, row.glyphs.len() as u32 - 1));
762
            }
763 764

            if queue_success {
765 766 767 768
                let glyph_count = draw_and_upload.len();

                if self.multithread && glyph_count > 1 {
                    // multithread rasterization
Alex Butler's avatar
Alex Butler committed
769
                    use crossbeam_deque::{Pop, Steal};
770 771 772 773
                    use std::{
                        mem,
                        sync::mpsc::{self, TryRecvError},
                    };
774 775 776 777 778 779 780 781 782 783 784 785

                    let (main, stealer) = crossbeam_deque::fifo();
                    let (to_main, from_stealers) = mpsc::channel();
                    let pad_glyphs = self.pad_glyphs;

                    for el in draw_and_upload {
                        main.push(el);
                    }
                    crossbeam_utils::thread::scope(|scope| {
                        for _ in 0..num_cpus::get().min(glyph_count).saturating_sub(1) {
                            let stealer = stealer.clone();
                            let to_main = to_main.clone();
Alex Butler's avatar
Alex Butler committed
786
                            scope.spawn(move |_| loop {
787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819
                                match stealer.steal() {
                                    Steal::Data((tex_coords, glyph)) => {
                                        let pixels = draw_glyph(tex_coords, glyph, pad_glyphs);
                                        to_main.send((tex_coords, pixels)).unwrap();
                                    }
                                    Steal::Empty => break,
                                    Steal::Retry => {}
                                }
                            });
                        }
                        mem::drop(to_main);

                        let mut workers_finished = false;
                        loop {
                            match main.pop() {
                                Pop::Data((tex_coords, glyph)) => {
                                    let pixels = draw_glyph(tex_coords, glyph, pad_glyphs);
                                    uploader(tex_coords, pixels.as_slice());
                                }
                                Pop::Empty if workers_finished => break,
                                _ => {}
                            }

                            while !workers_finished {
                                match from_stealers.try_recv() {
                                    Ok((tex_coords, pixels)) => {
                                        uploader(tex_coords, pixels.as_slice())
                                    }
                                    Err(TryRecvError::Disconnected) => workers_finished = true,
                                    Err(TryRecvError::Empty) => break,
                                }
                            }
                        }
Alex Butler's avatar
Alex Butler committed
820 821
                    })
                    .unwrap();
822 823 824 825 826
                } else {
                    // single thread rasterization
                    for (tex_coords, glyph) in draw_and_upload {
                        let pixels = draw_glyph(tex_coords, glyph, self.pad_glyphs);
                        uploader(tex_coords, pixels.as_slice());
827 828 829
                    }
                }
            }
830
        }
Alex Butler's avatar
Alex Butler committed
831

832 833 834
        if queue_success {
            self.queue.clear();
            Ok(())
Jim Blandy's avatar
Jim Blandy committed
835
        } else {
836
            // clear the cache then try again with optimal packing
837
            self.clear();
838
            self.cache_queued(uploader)
839 840
        }
    }
841

Jim Blandy's avatar
Jim Blandy committed
842 843
    /// Retrieves the (floating point) texture coordinates of the quad for a
    /// glyph in the cache, as well as the pixel-space (integer) coordinates
844 845 846
    /// that this region should be drawn at. These pixel-space coordinates
    /// assume an origin at the top left of the quad. In the majority of cases
    /// these pixel-space coordinates should be identical to the bounding box of
847
    /// the input glyph. They only differ if the cache has returned a substitute
Jim Blandy's avatar
Jim Blandy committed
848 849
    /// glyph that is deemed close enough to the requested glyph as specified by
    /// the cache tolerance parameters.
850
    ///
Jim Blandy's avatar
Jim Blandy committed
851 852
    /// A sucessful result is `Some` if the glyph is not an empty glyph (no
    /// shape, and thus no rect to return).
853
    ///
Jim Blandy's avatar
Jim Blandy committed
854 855
    /// Ensure that `font_id` matches the `font_id` that was passed to
    /// `queue_glyph` with this `glyph`.
Alex Butler's avatar
Alex Butler committed
856 857
    pub fn rect_for(
        &self,
858 859
        font_id: usize,
        glyph: &PositionedGlyph,
Alex Butler's avatar
Alex Butler committed
860
    ) -> Result<Option<TextureCoords>, CacheReadErr> {
Alex Butler's avatar
Alex Butler committed
861 862 863
        if glyph.pixel_bounding_box().is_none() {
            return Ok(None);
        }
864

865 866
        let (row, index) = self
            .all_glyphs
867 868
            .get(&self.lossy_info_for(font_id, glyph))
            .ok_or(CacheReadErr::GlyphNotCached)?;
869

Alex Butler's avatar
Alex Butler committed
870
        let (tex_width, tex_height) = (self.width as f32, self.height as f32);
Alex Butler's avatar
Alex Butler committed
871

872 873 874 875 876
        let GlyphTexInfo {
            tex_coords: mut tex_rect,
            offset: tex_offset,
            ..
        } = self.rows[&row].glyphs[*index as usize];
877 878 879
        if self.pad_glyphs {
            tex_rect = tex_rect.unpadded();
        }
880
        let uv_rect = Rect {
Jim Blandy's avatar
Jim Blandy committed
881
            min: point(
Alex Butler's avatar
Alex Butler committed
882 883
                tex_rect.min.x as f32 / tex_width,
                tex_rect.min.y as f32 / tex_height,
Jim Blandy's avatar
Jim Blandy committed
884 885
            ),
            max: point(
Alex Butler's avatar
Alex Butler committed
886 887
                tex_rect.max.x as f32 / tex_width,
                tex_rect.max.y as f32 / tex_height,
Jim Blandy's avatar
Jim Blandy committed
888
            ),
889
        };
890

891
        let local_bb = glyph
Jim Blandy's avatar
Jim Blandy committed
892 893
            .unpositioned()
            .clone()
894
            .positioned(point(0.0, 0.0) + tex_offset)
Jim Blandy's avatar
Jim Blandy committed
895 896
            .pixel_bounding_box()
            .unwrap();
Alex Butler's avatar
Alex Butler committed
897
        let min_from_origin =
898
            point(local_bb.min.x as f32, local_bb.min.y as f32) - (point(0.0, 0.0) + tex_offset);
Alex Butler's avatar
Alex Butler committed
899
        let ideal_min = min_from_origin + glyph.position();
900 901 902
        let min = point(ideal_min.x.round() as i32, ideal_min.y.round() as i32);
        let bb_offset = min - local_bb.min;
        let bb = Rect {
Jim Blandy's avatar
Jim Blandy committed
903 904
            min,
            max: local_bb.max + bb_offset,
905 906 907 908 909
        };
        Ok(Some((uv_rect, bb)))
    }
}

910
#[inline]
Alex Butler's avatar
Alex Butler committed
911
fn draw_glyph(
912
    tex_coords: Rect<u32>,
Alex Butler's avatar
Alex Butler committed
913
    glyph: &PositionedGlyph<'_>,
914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931
    pad_glyphs: bool,
) -> ByteArray2d {
    let mut pixels = ByteArray2d::zeros(tex_coords.height() as usize, tex_coords.width() as usize);
    if pad_glyphs {
        glyph.draw(|x, y, v| {
            let v = (v * 255.0).round().max(0.0).min(255.0) as u8;
            // `+ 1` accounts for top/left glyph padding
            pixels[(y as usize + 1, x as usize + 1)] = v;
        });
    } else {
        glyph.draw(|x, y, v| {
            let v = (v * 255.0).round().max(0.0).min(255.0) as u8;
            pixels[(y as usize, x as usize)] = v;
        });
    }
    pixels
}

932
#[cfg(test)]
933
mod test {
934
    use super::*;
Alex Butler's avatar
Alex Butler committed
935 936
    use crate::{Font, FontCollection, Scale};
    use approx::*;
937

938 939 940 941 942 943 944
    #[test]
    fn cache_test() {
        let font_data = include_bytes!("../fonts/wqy-microhei/WenQuanYiMicroHei.ttf");
        let font = FontCollection::from_bytes(font_data as &[u8])
            .unwrap()
            .into_font()
            .unwrap();
945 946 947 948 949 950 951

        let mut cache = Cache::builder()
            .dimensions(32, 32)
            .scale_tolerance(0.1)
            .position_tolerance(0.1)
            .pad_glyphs(false)
            .build();
952 953 954 955 956 957 958 959 960 961 962 963
        let strings = [
            ("Hello World!", 15.0),
            ("Hello World!", 14.0),
            ("Hello World!", 10.0),
            ("Hello World!", 15.0),
            ("Hello World!", 14.0),
            ("Hello World!", 10.0),
        ];
        for &(string, scale) in &strings {
            println!("Caching {:?}", (string, scale));
            for glyph in font.layout(string, Scale::uniform(scale), point(0.0, 0.0)) {
                cache.queue_glyph(0, glyph);
964
            }
965 966
            cache.cache_queued(|_, _| {}).unwrap();
        }
967 968
    }

969 970 971 972
    #[test]
    fn need_to_check_whole_cache() {
        let font_data = include_bytes!("../fonts/wqy-microhei/WenQuanYiMicroHei.ttf");
        let font = Font::from_bytes(font_data as &[u8]).unwrap();
973

974
        let glyph = font.glyph('l');
975

976 977 978 979 980 981
        let small = glyph.clone().scaled(Scale::uniform(10.0));
        let large = glyph.clone().scaled(Scale::uniform(10.05));

        let small_left = small.clone().positioned(point(0.0, 0.0));
        let large_left = large.clone().positioned(point(0.0, 0.0));
        let large_right = large.clone().positioned(point(-0.2, 0.0));
982

983 984 985 986 987 988
        let mut cache = Cache::builder()
            .dimensions(32, 32)
            .scale_tolerance(0.1)
            .position_tolerance(0.1)
            .pad_glyphs(false)
            .build();
Alex Butler's avatar
Alex Butler committed
989

990 991 992 993
        cache.queue_glyph(0, small_left.clone());
        // Next line is noop since it's within the scale tolerance of small_left:
        cache.queue_glyph(0, large_left.clone());
        cache.queue_glyph(0, large_right.clone());
Alex Butler's avatar
Alex Butler committed
994

995 996 997 998 999
        cache.cache_queued(|_, _| {}).unwrap();

        cache.rect_for(0, &small_left).unwrap();
        cache.rect_for(0, &large_left).unwrap();
        cache.rect_for(0, &large_right).unwrap();
1000 1001
    }

1002 1003 1004 1005 1006
    #[test]
    fn lossy_info() {
        let font_data = include_bytes!("../fonts/wqy-microhei/WenQuanYiMicroHei.ttf");
        let font = Font::from_bytes(font_data as &[u8]).unwrap();
        let glyph = font.glyph('l');
1007

1008 1009 1010 1011
        let small = glyph.clone().scaled(Scale::uniform(9.91));
        let near = glyph.clone().scaled(Scale::uniform(10.09));
        let far = glyph.clone().scaled(Scale::uniform(10.11));
        let really_far = glyph.clone().scaled(Scale::uniform(12.0));
1012

1013 1014 1015 1016
        let small_pos = small.clone().positioned(point(0.0, 0.0));
        let match_1 = near.clone().positioned(point(-10.0, -0.1));
        let match_2 = near.clone().positioned(point(5.1, 0.24));
        let match_3 = small.clone().positioned(point(-100.2, 50.1));
1017

1018 1019 1020
        let miss_1 = far.clone().positioned(point(0.0, 0.0));
        let miss_2 = really_far.clone().positioned(point(0.0, 0.0));
        let miss_3 = small.clone().positioned(point(0.3, 0.0));
1021

1022 1023 1024 1025
        let cache = Cache::builder()
            .scale_tolerance(0.2)
            .position_tolerance(0.5)
            .build();
1026

1027
        let small_info = cache.lossy_info_for(0, &small_pos);
1028

1029 1030 1031
        assert_eq!(small_info, cache.lossy_info_for(0, &match_1));
        assert_eq!(small_info, cache.lossy_info_for(0, &match_2));
        assert_eq!(small_info, cache.lossy_info_for(0, &match_3));
Alex Butler's avatar
Alex Butler committed
1032

1033 1034 1035
        assert_ne!(small_info, cache.lossy_info_for(0, &miss_1));
        assert_ne!(small_info, cache.lossy_info_for(0, &miss_2));
        assert_ne!(small_info, cache.lossy_info_for(0, &miss_3));
1036
    }
1037 1038 1039 1040

    #[test]
    fn cache_to_builder() {
        let cache = CacheBuilder {
1041
            dimensions: (32, 64),
1042 1043 1044
            scale_tolerance: 0.2,
            position_tolerance: 0.3,
            pad_glyphs: false,
1045
            multithread: false,
Alex Butler's avatar
Alex Butler committed
1046 1047
        }
        .build();
1048 1049 1050

        let to_builder: CacheBuilder = cache.to_builder();

1051
        assert_eq!(to_builder.dimensions, (32, 64));
1052 1053 1054
        assert_relative_eq!(to_builder.scale_tolerance, 0.2);
        assert_relative_eq!(to_builder.position_tolerance, 0.3);
        assert_eq!(to_builder.pad_glyphs, false);
1055
        assert_eq!(to_builder.multithread, false);
1056 1057 1058 1059
    }

    #[test]
    fn builder_rebuild() {
1060 1061 1062 1063 1064 1065 1066
        let mut cache = Cache::builder()
            .dimensions(32, 64)
            .scale_tolerance(0.2)
            .position_tolerance(0.3)
            .pad_glyphs(false)
            .multithread(true)
            .build();
1067 1068 1069

        let font = Font::from_bytes(
            include_bytes!("../fonts/wqy-microhei/WenQuanYiMicroHei.ttf") as &[u8],
Alex Butler's avatar
Alex Butler committed
1070 1071
        )
        .unwrap();
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086
        cache.queue_glyph(
            0,
            font.glyph('l')
                .scaled(Scale::uniform(25.0))
                .positioned(point(0.0, 0.0)),
        );
        cache.cache_queued(|_, _| {}).unwrap();

        cache.queue_glyph(
            0,
            font.glyph('a')
                .scaled(Scale::uniform(25.0))
                .positioned(point(0.0, 0.0)),
        );

1087 1088 1089 1090 1091 1092 1093
        Cache::builder()
            .dimensions(64, 128)
            .scale_tolerance(0.05)
            .position_tolerance(0.15)
            .pad_glyphs(true)
            .multithread(false)
            .rebuild(&mut cache);
1094 1095 1096 1097 1098 1099

        assert_eq!(cache.width, 64);
        assert_eq!(cache.height, 128);
        assert_relative_eq!(cache.scale_tolerance, 0.05);
        assert_relative_eq!(cache.position_tolerance, 0.15);
        assert_eq!(cache.pad_glyphs, true);
1100
        assert_eq!(cache.multithread, false);
1101 1102 1103 1104 1105 1106 1107 1108

        assert!(
            cache.all_glyphs.is_empty(),
            "cache should have been cleared"
        );

        assert_eq!(cache.queue.len(), 1, "cache should have an unchanged queue");
    }
1109
}