1use super::*;
2
3#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
9pub struct GlyphId(u32);
10
11impl GlyphId {
12 pub const fn new(value: u32) -> Self {
14 Self(value)
15 }
16
17 pub const fn value(self) -> u32 {
19 self.0
20 }
21}
22
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
25pub struct GlyphAtlasEntry {
26 glyph: GlyphId,
27 source: ImageTexelRect,
28}
29
30impl GlyphAtlasEntry {
31 pub const fn new(glyph: GlyphId, source: ImageTexelRect) -> Self {
33 Self { glyph, source }
34 }
35
36 pub const fn glyph(self) -> GlyphId {
38 self.glyph
39 }
40
41 pub const fn source(self) -> ImageTexelRect {
43 self.source
44 }
45}
46
47#[derive(Debug, Clone, Copy, PartialEq, Eq)]
49pub struct GlyphAtlasBudget {
50 image: ImageBudget,
51 max_entries: usize,
52 max_metadata_bytes: usize,
53}
54
55impl GlyphAtlasBudget {
56 pub fn new(
58 image: ImageBudget,
59 max_entries: usize,
60 max_metadata_bytes: usize,
61 ) -> Result<Self, GlyphError> {
62 if max_entries == 0 || max_metadata_bytes < std::mem::size_of::<GlyphAtlasEntry>() {
63 return Err(GlyphError::InvalidBudget);
64 }
65 Ok(Self {
66 image,
67 max_entries,
68 max_metadata_bytes,
69 })
70 }
71
72 pub const fn image(self) -> ImageBudget {
74 self.image
75 }
76
77 pub const fn max_entries(self) -> usize {
79 self.max_entries
80 }
81
82 pub const fn max_metadata_bytes(self) -> usize {
84 self.max_metadata_bytes
85 }
86}
87
88impl Default for GlyphAtlasBudget {
89 fn default() -> Self {
90 Self {
91 image: ImageBudget::default(),
92 max_entries: 65_536,
93 max_metadata_bytes: 4 * 1024 * 1024,
94 }
95 }
96}
97
98#[derive(Debug, Clone, Copy, PartialEq, Eq)]
100pub struct GlyphRunBudget {
101 max_glyphs: usize,
102 max_retained_bytes: usize,
103}
104
105impl GlyphRunBudget {
106 pub fn new(max_glyphs: usize, max_retained_bytes: usize) -> Result<Self, GlyphError> {
108 if max_glyphs == 0 || max_retained_bytes < glyph_retained_bytes(1).unwrap_or(usize::MAX) {
109 return Err(GlyphError::InvalidBudget);
110 }
111 Ok(Self {
112 max_glyphs,
113 max_retained_bytes,
114 })
115 }
116
117 pub const fn max_glyphs(self) -> usize {
119 self.max_glyphs
120 }
121
122 pub const fn max_retained_bytes(self) -> usize {
124 self.max_retained_bytes
125 }
126}
127
128impl Default for GlyphRunBudget {
129 fn default() -> Self {
130 Self {
131 max_glyphs: 100_000,
132 max_retained_bytes: 32 * 1024 * 1024,
133 }
134 }
135}
136
137#[derive(Debug, Clone, Copy, PartialEq, Eq)]
139pub enum GlyphError {
140 Image(ImageError),
142 InvalidBudget,
144 EntryBudgetExceeded {
146 limit: usize,
148 actual: usize,
150 },
151 MetadataBudgetExceeded {
153 limit: usize,
155 actual: usize,
157 },
158 DuplicateGlyph {
160 glyph: GlyphId,
162 },
163 OverlappingGlyph {
165 glyph: GlyphId,
167 conflicting_glyph: GlyphId,
169 },
170 MissingGlyph {
172 glyph: GlyphId,
174 index: usize,
176 },
177 InvalidGlyph,
179 AllocationFailed {
182 requested_bytes: usize,
184 },
185}
186
187impl fmt::Display for GlyphError {
188 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
189 match self {
190 Self::Image(error) => write!(formatter, "glyph image error: {error}"),
191 Self::InvalidBudget => write!(formatter, "glyph budget must fit one entry"),
192 Self::EntryBudgetExceeded { limit, actual } => {
193 write!(formatter, "glyph count {actual} exceeds limit {limit}")
194 }
195 Self::MetadataBudgetExceeded { limit, actual } => write!(
196 formatter,
197 "glyph recovery metadata requires {actual} bytes, over limit {limit}"
198 ),
199 Self::DuplicateGlyph { glyph } => {
200 write!(formatter, "glyph identity {} is duplicated", glyph.value())
201 }
202 Self::OverlappingGlyph {
203 glyph,
204 conflicting_glyph,
205 } => write!(
206 formatter,
207 "glyph identity {} overlaps atlas texels owned by glyph {}",
208 glyph.value(),
209 conflicting_glyph.value()
210 ),
211 Self::MissingGlyph { glyph, index } => write!(
212 formatter,
213 "glyph identity {} at run index {index} is absent from the atlas",
214 glyph.value()
215 ),
216 Self::InvalidGlyph => write!(formatter, "glyph placement or atlas region is invalid"),
217 Self::AllocationFailed { requested_bytes } => write!(
218 formatter,
219 "could not reserve {requested_bytes} bytes for glyph metadata or scratch storage"
220 ),
221 }
222 }
223}
224
225impl Error for GlyphError {}
226
227impl From<ImageError> for GlyphError {
228 fn from(error: ImageError) -> Self {
229 Self::Image(error)
230 }
231}
232
233#[derive(Debug, Clone, Copy, PartialEq, Eq)]
235pub struct GlyphUploadReport {
236 uploaded_bytes: usize,
237 inserted_entry: bool,
238}
239
240impl GlyphUploadReport {
241 pub const fn uploaded_bytes(self) -> usize {
243 self.uploaded_bytes
244 }
245
246 pub const fn inserted_entry(self) -> bool {
248 self.inserted_entry
249 }
250}
251
252pub struct GlyphAtlas2d {
258 pub(super) image: Image2d,
259 entries: Vec<GlyphAtlasEntry>,
260 budget: GlyphAtlasBudget,
261}
262
263impl GlyphAtlas2d {
264 pub const fn size(&self) -> (u32, u32) {
266 self.image.size()
267 }
268
269 pub fn entries(&self) -> &[GlyphAtlasEntry] {
271 &self.entries
272 }
273
274 pub fn source_for(&self, glyph: GlyphId) -> Option<ImageTexelRect> {
276 find_entry(&self.entries, glyph).map(GlyphAtlasEntry::source)
277 }
278
279 pub const fn budget(&self) -> GlyphAtlasBudget {
281 self.budget
282 }
283
284 pub fn recovery_memory_bytes(&self) -> usize {
286 self.image.recovery_memory_bytes().saturating_add(
287 self.entries
288 .capacity()
289 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>()),
290 )
291 }
292
293 pub fn gpu_allocation_bytes(&self) -> usize {
296 self.image.gpu_allocation_bytes()
297 }
298}
299
300#[derive(Debug, Clone, Copy, PartialEq)]
302pub struct PositionedGlyph2d {
303 glyph: GlyphId,
304 destination: LogicalViewportRegion,
305 tint: Color,
306}
307
308impl PositionedGlyph2d {
309 pub fn new(
311 glyph: GlyphId,
312 destination: LogicalViewportRegion,
313 tint: Color,
314 ) -> Result<Self, GlyphError> {
315 if !tint.is_normalized() || !logical_region_arithmetic_is_finite(destination) {
316 return Err(GlyphError::InvalidGlyph);
317 }
318 Ok(Self {
319 glyph,
320 destination,
321 tint,
322 })
323 }
324
325 pub const fn glyph(self) -> GlyphId {
327 self.glyph
328 }
329
330 pub const fn destination(self) -> LogicalViewportRegion {
332 self.destination
333 }
334
335 pub const fn tint(self) -> Color {
337 self.tint
338 }
339}
340
341#[derive(Debug, Clone, Copy, PartialEq)]
343pub struct GlyphRunBounds {
344 region: Option<LogicalViewportRegion>,
345}
346
347impl GlyphRunBounds {
348 pub const fn region(self) -> Option<LogicalViewportRegion> {
350 self.region
351 }
352
353 pub const fn is_empty(self) -> bool {
355 self.region.is_none()
356 }
357}
358
359#[derive(Debug, Clone, Copy, PartialEq, Eq)]
361pub struct GlyphRunStatistics {
362 submitted_glyphs: usize,
363 rendered_quads: usize,
364 atlas_misses: usize,
365 retained_bytes: usize,
366}
367
368impl GlyphRunStatistics {
369 pub const fn submitted_glyphs(self) -> usize {
371 self.submitted_glyphs
372 }
373
374 pub const fn rendered_quads(self) -> usize {
376 self.rendered_quads
377 }
378
379 pub const fn atlas_misses(self) -> usize {
381 self.atlas_misses
382 }
383
384 pub const fn retained_bytes(self) -> usize {
386 self.retained_bytes
387 }
388}
389
390pub struct GlyphRun2d {
397 pub(super) batch: ImageBatch2d,
398 glyphs: Vec<PositionedGlyph2d>,
399 bounds: GlyphRunBounds,
400 budget: GlyphRunBudget,
401}
402
403impl GlyphRun2d {
404 pub fn glyphs(&self) -> &[PositionedGlyph2d] {
406 &self.glyphs
407 }
408
409 pub fn glyph_count(&self) -> usize {
411 self.glyphs.len()
412 }
413
414 pub const fn bounds(&self) -> GlyphRunBounds {
416 self.bounds
417 }
418
419 pub const fn budget(&self) -> GlyphRunBudget {
421 self.budget
422 }
423
424 pub fn statistics(&self) -> GlyphRunStatistics {
426 GlyphRunStatistics {
427 submitted_glyphs: self.glyphs.len(),
428 rendered_quads: self.glyphs.len(),
429 atlas_misses: 0,
430 retained_bytes: self.recovery_memory_bytes(),
431 }
432 }
433
434 pub fn recovery_memory_bytes(&self) -> usize {
436 self.glyphs
437 .capacity()
438 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
439 .saturating_add(self.batch.recovery_memory_bytes())
440 }
441
442 pub fn gpu_allocation_bytes(&self) -> usize {
444 self.batch.gpu_allocation_bytes()
445 }
446}
447
448impl WgpuRenderer {
449 pub fn create_glyph_atlas(
451 &self,
452 width: u32,
453 height: u32,
454 pixels: Vec<u8>,
455 entries: Vec<GlyphAtlasEntry>,
456 budget: GlyphAtlasBudget,
457 ) -> Result<GlyphAtlas2d, GlyphError> {
458 create_glyph_atlas_resources(
459 &self.device,
460 &self.queue,
461 Arc::clone(&self.renderer_identity),
462 width,
463 height,
464 pixels,
465 entries,
466 budget,
467 )
468 }
469
470 pub fn upload_glyph(
476 &self,
477 atlas: &mut GlyphAtlas2d,
478 entry: GlyphAtlasEntry,
479 pixels: &[u8],
480 ) -> Result<GlyphUploadReport, GlyphError> {
481 self.validate_image(&atlas.image)?;
482 if !entry.source.fits(atlas.image.width(), atlas.image.height()) {
483 return Err(GlyphError::InvalidGlyph);
484 }
485 image::validate_image_region_upload(&atlas.image, entry.source, pixels.len())?;
486 let insertion = validate_glyph_insertion(&atlas.entries, entry)?;
487 if insertion.is_some() {
488 validate_metadata_capacity(atlas.entries.len().saturating_add(1), atlas.budget)?;
489 }
490 let replacement_entries = if let Some(index) = insertion {
491 let new_len = atlas.entries.len() + 1;
492 let requested_bytes = new_len
493 .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
494 .ok_or(GlyphError::InvalidGlyph)?;
495 let mut replacement = Vec::new();
496 replacement
497 .try_reserve_exact(new_len)
498 .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
499 replacement.extend_from_slice(&atlas.entries[..index]);
500 replacement.push(entry);
501 replacement.extend_from_slice(&atlas.entries[index..]);
502 let actual = replacement
503 .capacity()
504 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
505 if actual > atlas.budget.max_metadata_bytes {
506 return Err(GlyphError::MetadataBudgetExceeded {
507 limit: atlas.budget.max_metadata_bytes,
508 actual,
509 });
510 }
511 Some(replacement)
512 } else {
513 None
514 };
515 let report = self.update_image_region(&mut atlas.image, entry.source, pixels)?;
516 if let Some(replacement) = replacement_entries {
517 atlas.entries = replacement;
518 }
519 Ok(GlyphUploadReport {
520 uploaded_bytes: report.uploaded_bytes(),
521 inserted_entry: insertion.is_some(),
522 })
523 }
524
525 pub fn create_glyph_run(
527 &self,
528 atlas: &GlyphAtlas2d,
529 glyphs: Vec<PositionedGlyph2d>,
530 budget: GlyphRunBudget,
531 ) -> Result<GlyphRun2d, GlyphError> {
532 self.validate_image(&atlas.image)?;
533 create_glyph_run_resources(
534 &self.device,
535 &self.queue,
536 Arc::clone(&self.renderer_identity),
537 atlas,
538 glyphs,
539 budget,
540 )
541 }
542
543 pub fn restore_glyph_atlas(&self, source: &GlyphAtlas2d) -> Result<GlyphAtlas2d, GlyphError> {
545 image::validate_image_shape(
546 source.image.width(),
547 source.image.height(),
548 source.image.pixels().len(),
549 source.budget.image,
550 self.device.limits().max_texture_dimension_2d,
551 )?;
552 let mut entries = Vec::new();
553 entries
554 .try_reserve_exact(source.entries.len())
555 .map_err(|_| GlyphError::AllocationFailed {
556 requested_bytes: std::mem::size_of_val(source.entries.as_slice()),
557 })?;
558 entries.extend_from_slice(&source.entries);
559 validate_atlas_entries(
560 &mut entries,
561 source.image.width(),
562 source.image.height(),
563 source.budget,
564 )?;
565 entries = compact_glyph_vec(entries, source.budget.max_metadata_bytes)?;
566 let actual = entries
567 .capacity()
568 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
569 if actual > source.budget.max_metadata_bytes {
570 return Err(GlyphError::MetadataBudgetExceeded {
571 limit: source.budget.max_metadata_bytes,
572 actual,
573 });
574 }
575 let image = self.restore_image(&source.image)?;
576 Ok(GlyphAtlas2d {
577 image,
578 entries,
579 budget: source.budget,
580 })
581 }
582
583 pub fn restore_glyph_run(
585 &self,
586 atlas: &GlyphAtlas2d,
587 source: &GlyphRun2d,
588 ) -> Result<GlyphRun2d, GlyphError> {
589 self.validate_image(&atlas.image)?;
590 if !Arc::ptr_eq(
591 &atlas.image.recovery_identity,
592 &source.batch.image_recovery_identity,
593 ) {
594 return Err(ImageError::RecoverySourceMismatch.into());
595 }
596 validate_glyph_run_sources(&atlas.entries, &source.glyphs, source.batch.sprites())?;
597 validate_glyph_run_budget(source.glyphs.len(), source.budget)?;
598 validate_glyph_membership(&atlas.entries, &source.glyphs)?;
599 measure_glyphs(&source.glyphs)?;
600 let batch_budget =
601 ImageBatchBudget::new(source.budget.max_glyphs, source.budget.max_retained_bytes)?;
602 image::preflight_image_batch_capacity(&self.device, source.glyphs.len(), batch_budget)?;
603 let retained_bytes = source
604 .glyphs
605 .len()
606 .checked_mul(std::mem::size_of::<PositionedGlyph2d>())
607 .ok_or(GlyphError::InvalidGlyph)?;
608 let mut glyphs = Vec::new();
609 glyphs.try_reserve_exact(source.glyphs.len()).map_err(|_| {
610 GlyphError::AllocationFailed {
611 requested_bytes: retained_bytes,
612 }
613 })?;
614 glyphs.extend_from_slice(&source.glyphs);
615 self.create_glyph_run(atlas, glyphs, source.budget)
616 }
617
618 pub(super) fn validate_glyph_run(
619 &self,
620 atlas: &GlyphAtlas2d,
621 run: &GlyphRun2d,
622 ) -> Result<(), GlyphError> {
623 self.validate_image_batch(&atlas.image, &run.batch)?;
624 Ok(())
625 }
626}
627
628#[allow(clippy::too_many_arguments)]
629pub(super) fn create_glyph_atlas_resources(
630 device: &wgpu::Device,
631 queue: &wgpu::Queue,
632 renderer_identity: Arc<()>,
633 width: u32,
634 height: u32,
635 pixels: Vec<u8>,
636 mut entries: Vec<GlyphAtlasEntry>,
637 budget: GlyphAtlasBudget,
638) -> Result<GlyphAtlas2d, GlyphError> {
639 image::validate_image_shape(
640 width,
641 height,
642 pixels.len(),
643 budget.image,
644 device.limits().max_texture_dimension_2d,
645 )?;
646 validate_atlas_entries(&mut entries, width, height, budget)?;
647 entries = compact_glyph_vec(entries, budget.max_metadata_bytes)?;
648 let actual_metadata_bytes = entries
649 .capacity()
650 .saturating_mul(std::mem::size_of::<GlyphAtlasEntry>());
651 if actual_metadata_bytes > budget.max_metadata_bytes {
652 return Err(GlyphError::MetadataBudgetExceeded {
653 limit: budget.max_metadata_bytes,
654 actual: actual_metadata_bytes,
655 });
656 }
657 let image = image::create_image_resources(
658 device,
659 queue,
660 renderer_identity,
661 width,
662 height,
663 pixels,
664 budget.image,
665 )?;
666 Ok(GlyphAtlas2d {
667 image,
668 entries,
669 budget,
670 })
671}
672
673pub(super) fn create_glyph_run_resources(
674 device: &wgpu::Device,
675 queue: &wgpu::Queue,
676 renderer_identity: Arc<()>,
677 atlas: &GlyphAtlas2d,
678 glyphs: Vec<PositionedGlyph2d>,
679 budget: GlyphRunBudget,
680) -> Result<GlyphRun2d, GlyphError> {
681 validate_glyph_run_budget(glyphs.len(), budget)?;
682 validate_glyph_membership(&atlas.entries, &glyphs)?;
683 let bounds = measure_glyphs(&glyphs)?;
684 let batch_budget = ImageBatchBudget::new(budget.max_glyphs, budget.max_retained_bytes)?;
685 image::preflight_image_batch_capacity(device, glyphs.len(), batch_budget)?;
686 let glyphs = compact_glyph_vec(glyphs, budget.max_retained_bytes)?;
687 let sprites = resolve_glyph_sprites(&atlas.entries, &glyphs)?;
688 let actual_retained_bytes = glyphs
689 .capacity()
690 .saturating_mul(std::mem::size_of::<PositionedGlyph2d>())
691 .saturating_add(
692 sprites
693 .capacity()
694 .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
695 );
696 if actual_retained_bytes > budget.max_retained_bytes {
697 return Err(GlyphError::MetadataBudgetExceeded {
698 limit: budget.max_retained_bytes,
699 actual: actual_retained_bytes,
700 });
701 }
702 let batch = image::create_image_batch_resources(
703 device,
704 queue,
705 renderer_identity,
706 &atlas.image,
707 sprites,
708 batch_budget,
709 )?;
710 Ok(GlyphRun2d {
711 batch,
712 glyphs,
713 bounds,
714 budget,
715 })
716}
717
718fn compact_glyph_vec<T: Copy>(values: Vec<T>, maximum_bytes: usize) -> Result<Vec<T>, GlyphError> {
719 if values.capacity().saturating_mul(std::mem::size_of::<T>()) <= maximum_bytes {
720 return Ok(values);
721 }
722 let requested_bytes = values
723 .len()
724 .checked_mul(std::mem::size_of::<T>())
725 .ok_or(GlyphError::InvalidGlyph)?;
726 let mut compact = Vec::new();
727 compact
728 .try_reserve_exact(values.len())
729 .map_err(|_| GlyphError::AllocationFailed { requested_bytes })?;
730 compact.extend_from_slice(&values);
731 Ok(compact)
732}
733
734fn validate_atlas_entries(
735 entries: &mut [GlyphAtlasEntry],
736 width: u32,
737 height: u32,
738 budget: GlyphAtlasBudget,
739) -> Result<(), GlyphError> {
740 validate_metadata_capacity(entries.len(), budget)?;
741 entries.sort_unstable_by_key(|entry| entry.glyph);
742 for (index, entry) in entries.iter().enumerate() {
743 if !entry.source.fits(width, height) {
744 return Err(GlyphError::InvalidGlyph);
745 }
746 if index > 0 && entries[index - 1].glyph == entry.glyph {
747 return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
748 }
749 }
750 validate_non_overlapping_glyph_entries(entries)
751}
752
753#[derive(Clone, Copy)]
754struct GlyphSweepEvent {
755 x: u32,
756 starts: bool,
757 entry_index: usize,
758 minimum_y: u32,
759 maximum_y: u32,
760}
761
762fn validate_non_overlapping_glyph_entries(entries: &[GlyphAtlasEntry]) -> Result<(), GlyphError> {
763 if entries.len() < 2 {
764 return Ok(());
765 }
766 let endpoint_count = entries
767 .len()
768 .checked_mul(2)
769 .ok_or(GlyphError::InvalidGlyph)?;
770 let mut events = Vec::new();
771 events
772 .try_reserve_exact(endpoint_count)
773 .map_err(|_| GlyphError::AllocationFailed {
774 requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<GlyphSweepEvent>()),
775 })?;
776 let mut vertical_coordinates = Vec::new();
777 vertical_coordinates
778 .try_reserve_exact(endpoint_count)
779 .map_err(|_| GlyphError::AllocationFailed {
780 requested_bytes: endpoint_count.saturating_mul(std::mem::size_of::<u32>()),
781 })?;
782 for (entry_index, entry) in entries.iter().copied().enumerate() {
783 let source = entry.source;
784 let maximum_x = source
785 .x()
786 .checked_add(source.width())
787 .ok_or(GlyphError::InvalidGlyph)?;
788 let maximum_y = source
789 .y()
790 .checked_add(source.height())
791 .ok_or(GlyphError::InvalidGlyph)?;
792 events.push(GlyphSweepEvent {
793 x: source.x(),
794 starts: true,
795 entry_index,
796 minimum_y: source.y(),
797 maximum_y,
798 });
799 events.push(GlyphSweepEvent {
800 x: maximum_x,
801 starts: false,
802 entry_index,
803 minimum_y: source.y(),
804 maximum_y,
805 });
806 vertical_coordinates.push(source.y());
807 vertical_coordinates.push(maximum_y);
808 }
809 events.sort_unstable_by_key(|event| (event.x, event.starts));
812 vertical_coordinates.sort_unstable();
813 vertical_coordinates.dedup();
814 let interval_count = vertical_coordinates.len().saturating_sub(1);
815 let tree_len = interval_count
816 .checked_mul(4)
817 .and_then(|value| value.checked_add(4))
818 .ok_or(GlyphError::InvalidGlyph)?;
819 let mut maximum_coverage = Vec::new();
820 maximum_coverage
821 .try_reserve_exact(tree_len)
822 .map_err(|_| GlyphError::AllocationFailed {
823 requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
824 })?;
825 maximum_coverage.resize(tree_len, 0_i32);
826 let mut lazy_coverage = Vec::new();
827 lazy_coverage
828 .try_reserve_exact(tree_len)
829 .map_err(|_| GlyphError::AllocationFailed {
830 requested_bytes: tree_len.saturating_mul(std::mem::size_of::<i32>()),
831 })?;
832 lazy_coverage.resize(tree_len, 0_i32);
833 let mut active = Vec::new();
834 active
835 .try_reserve_exact(entries.len())
836 .map_err(|_| GlyphError::AllocationFailed {
837 requested_bytes: entries.len().saturating_mul(std::mem::size_of::<bool>()),
838 })?;
839 active.resize(entries.len(), false);
840
841 for event in events {
842 let minimum = vertical_coordinates
843 .binary_search(&event.minimum_y)
844 .expect("glyph sweep endpoints came from the coordinate set");
845 let maximum = vertical_coordinates
846 .binary_search(&event.maximum_y)
847 .expect("glyph sweep endpoints came from the coordinate set");
848 if event.starts {
849 if glyph_coverage_max(
850 &maximum_coverage,
851 &lazy_coverage,
852 1,
853 0,
854 interval_count,
855 minimum,
856 maximum,
857 ) > 0
858 {
859 let entry = entries[event.entry_index];
860 let conflict = active
861 .iter()
862 .enumerate()
863 .find(|(index, active)| {
864 **active && glyph_rectangles_overlap(entries[*index].source, entry.source)
865 })
866 .map(|(index, _)| entries[index].glyph)
867 .expect("positive sweep coverage has an active owning glyph");
868 return Err(GlyphError::OverlappingGlyph {
869 glyph: entry.glyph,
870 conflicting_glyph: conflict,
871 });
872 }
873 glyph_coverage_add(
874 &mut maximum_coverage,
875 &mut lazy_coverage,
876 1,
877 0,
878 interval_count,
879 minimum,
880 maximum,
881 1,
882 );
883 active[event.entry_index] = true;
884 } else {
885 glyph_coverage_add(
886 &mut maximum_coverage,
887 &mut lazy_coverage,
888 1,
889 0,
890 interval_count,
891 minimum,
892 maximum,
893 -1,
894 );
895 active[event.entry_index] = false;
896 }
897 }
898 Ok(())
899}
900
901#[allow(clippy::too_many_arguments)]
902fn glyph_coverage_add(
903 maximum_coverage: &mut [i32],
904 lazy_coverage: &mut [i32],
905 node: usize,
906 left: usize,
907 right: usize,
908 query_left: usize,
909 query_right: usize,
910 amount: i32,
911) {
912 if query_left <= left && right <= query_right {
913 maximum_coverage[node] += amount;
914 lazy_coverage[node] += amount;
915 return;
916 }
917 let middle = left + (right - left) / 2;
918 if query_left < middle {
919 glyph_coverage_add(
920 maximum_coverage,
921 lazy_coverage,
922 node * 2,
923 left,
924 middle,
925 query_left,
926 query_right,
927 amount,
928 );
929 }
930 if query_right > middle {
931 glyph_coverage_add(
932 maximum_coverage,
933 lazy_coverage,
934 node * 2 + 1,
935 middle,
936 right,
937 query_left,
938 query_right,
939 amount,
940 );
941 }
942 maximum_coverage[node] =
943 lazy_coverage[node] + maximum_coverage[node * 2].max(maximum_coverage[node * 2 + 1]);
944}
945
946#[allow(clippy::too_many_arguments)]
947fn glyph_coverage_max(
948 maximum_coverage: &[i32],
949 lazy_coverage: &[i32],
950 node: usize,
951 left: usize,
952 right: usize,
953 query_left: usize,
954 query_right: usize,
955) -> i32 {
956 if query_left <= left && right <= query_right {
957 return maximum_coverage[node];
958 }
959 let middle = left + (right - left) / 2;
960 let mut maximum = 0;
961 if query_left < middle {
962 maximum = maximum.max(glyph_coverage_max(
963 maximum_coverage,
964 lazy_coverage,
965 node * 2,
966 left,
967 middle,
968 query_left,
969 query_right,
970 ));
971 }
972 if query_right > middle {
973 maximum = maximum.max(glyph_coverage_max(
974 maximum_coverage,
975 lazy_coverage,
976 node * 2 + 1,
977 middle,
978 right,
979 query_left,
980 query_right,
981 ));
982 }
983 lazy_coverage[node] + maximum
984}
985
986fn validate_glyph_insertion(
987 entries: &[GlyphAtlasEntry],
988 entry: GlyphAtlasEntry,
989) -> Result<Option<usize>, GlyphError> {
990 match entries.binary_search_by_key(&entry.glyph, |candidate| candidate.glyph) {
991 Ok(index) => {
992 if entries[index].source != entry.source {
993 return Err(GlyphError::DuplicateGlyph { glyph: entry.glyph });
994 }
995 Ok(None)
996 }
997 Err(index) => {
998 if let Some(conflict) = entries
999 .iter()
1000 .find(|candidate| glyph_rectangles_overlap(candidate.source, entry.source))
1001 {
1002 return Err(GlyphError::OverlappingGlyph {
1003 glyph: entry.glyph,
1004 conflicting_glyph: conflict.glyph,
1005 });
1006 }
1007 Ok(Some(index))
1008 }
1009 }
1010}
1011
1012fn glyph_rectangles_overlap(left: ImageTexelRect, right: ImageTexelRect) -> bool {
1013 let left_max_x = u64::from(left.x()) + u64::from(left.width());
1014 let left_max_y = u64::from(left.y()) + u64::from(left.height());
1015 let right_max_x = u64::from(right.x()) + u64::from(right.width());
1016 let right_max_y = u64::from(right.y()) + u64::from(right.height());
1017 u64::from(left.x()) < right_max_x
1018 && u64::from(right.x()) < left_max_x
1019 && u64::from(left.y()) < right_max_y
1020 && u64::from(right.y()) < left_max_y
1021}
1022
1023fn validate_metadata_capacity(
1024 entry_count: usize,
1025 budget: GlyphAtlasBudget,
1026) -> Result<(), GlyphError> {
1027 if entry_count > budget.max_entries {
1028 return Err(GlyphError::EntryBudgetExceeded {
1029 limit: budget.max_entries,
1030 actual: entry_count,
1031 });
1032 }
1033 let bytes = entry_count
1034 .checked_mul(std::mem::size_of::<GlyphAtlasEntry>())
1035 .ok_or(GlyphError::InvalidGlyph)?;
1036 if bytes > budget.max_metadata_bytes {
1037 return Err(GlyphError::MetadataBudgetExceeded {
1038 limit: budget.max_metadata_bytes,
1039 actual: bytes,
1040 });
1041 }
1042 Ok(())
1043}
1044
1045fn validate_glyph_run_budget(glyph_count: usize, budget: GlyphRunBudget) -> Result<(), GlyphError> {
1046 if glyph_count > budget.max_glyphs {
1047 return Err(GlyphError::EntryBudgetExceeded {
1048 limit: budget.max_glyphs,
1049 actual: glyph_count,
1050 });
1051 }
1052 let retained_bytes = glyph_retained_bytes(glyph_count).ok_or(GlyphError::InvalidGlyph)?;
1053 if retained_bytes > budget.max_retained_bytes {
1054 return Err(GlyphError::MetadataBudgetExceeded {
1055 limit: budget.max_retained_bytes,
1056 actual: retained_bytes,
1057 });
1058 }
1059 Ok(())
1060}
1061
1062fn glyph_retained_bytes(glyph_count: usize) -> Option<usize> {
1063 let glyph_bytes = glyph_count.checked_mul(std::mem::size_of::<PositionedGlyph2d>())?;
1064 let sprite_bytes = glyph_count.checked_mul(std::mem::size_of::<ImageSprite2d>())?;
1065 glyph_bytes.checked_add(sprite_bytes)
1066}
1067
1068fn find_entry(entries: &[GlyphAtlasEntry], glyph: GlyphId) -> Option<GlyphAtlasEntry> {
1069 entries
1070 .binary_search_by_key(&glyph, |entry| entry.glyph)
1071 .ok()
1072 .map(|index| entries[index])
1073}
1074
1075fn resolve_glyph_sprites(
1076 entries: &[GlyphAtlasEntry],
1077 glyphs: &[PositionedGlyph2d],
1078) -> Result<Vec<ImageSprite2d>, GlyphError> {
1079 validate_glyph_membership(entries, glyphs)?;
1080 let mut sprites = Vec::new();
1081 sprites
1082 .try_reserve_exact(glyphs.len())
1083 .map_err(|_| GlyphError::AllocationFailed {
1084 requested_bytes: glyphs
1085 .len()
1086 .saturating_mul(std::mem::size_of::<ImageSprite2d>()),
1087 })?;
1088 for (index, glyph) in glyphs.iter().copied().enumerate() {
1089 let source = find_entry(entries, glyph.glyph)
1090 .map(GlyphAtlasEntry::source)
1091 .ok_or(GlyphError::MissingGlyph {
1093 glyph: glyph.glyph,
1094 index,
1095 })?;
1096 sprites.push(ImageSprite2d::new(source, glyph.destination, glyph.tint)?);
1097 }
1098 Ok(sprites)
1099}
1100
1101fn validate_glyph_membership(
1102 entries: &[GlyphAtlasEntry],
1103 glyphs: &[PositionedGlyph2d],
1104) -> Result<(), GlyphError> {
1105 if let Some((index, glyph)) = glyphs
1106 .iter()
1107 .enumerate()
1108 .find(|(_, glyph)| find_entry(entries, glyph.glyph).is_none())
1109 {
1110 return Err(GlyphError::MissingGlyph {
1111 glyph: glyph.glyph,
1112 index,
1113 });
1114 }
1115 Ok(())
1116}
1117
1118fn validate_glyph_run_sources(
1119 entries: &[GlyphAtlasEntry],
1120 glyphs: &[PositionedGlyph2d],
1121 sprites: &[ImageSprite2d],
1122) -> Result<(), GlyphError> {
1123 if glyphs.len() != sprites.len()
1124 || glyphs.iter().zip(sprites).any(|(glyph, sprite)| {
1125 find_entry(entries, glyph.glyph).map(GlyphAtlasEntry::source) != Some(sprite.source())
1126 })
1127 {
1128 return Err(ImageError::RecoverySourceMismatch.into());
1129 }
1130 Ok(())
1131}
1132
1133fn measure_glyphs(glyphs: &[PositionedGlyph2d]) -> Result<GlyphRunBounds, GlyphError> {
1134 if glyphs
1135 .iter()
1136 .any(|glyph| !image::logical_image_region_is_portable(glyph.destination))
1137 {
1138 return Err(GlyphError::InvalidGlyph);
1139 }
1140 let Some(first) = glyphs.first().copied() else {
1141 return Ok(GlyphRunBounds { region: None });
1142 };
1143 let first_origin = first.destination.origin().to_vec2();
1144 let first_size = first.destination.viewport().size();
1145 let mut minimum = first_origin;
1146 let mut maximum = first_origin + first_size;
1147 for glyph in &glyphs[1..] {
1148 if !logical_region_arithmetic_is_finite(glyph.destination) {
1149 return Err(GlyphError::InvalidGlyph);
1150 }
1151 let origin = glyph.destination.origin().to_vec2();
1152 let end = origin + glyph.destination.viewport().size();
1153 minimum.x = minimum.x.min(origin.x);
1154 minimum.y = minimum.y.min(origin.y);
1155 maximum.x = maximum.x.max(end.x);
1156 maximum.y = maximum.y.max(end.y);
1157 }
1158 if !minimum.is_finite() || !maximum.is_finite() {
1159 return Err(GlyphError::InvalidGlyph);
1160 }
1161 let viewport = LogicalViewport::new(maximum.x - minimum.x, maximum.y - minimum.y)
1162 .map_err(|_| GlyphError::InvalidGlyph)?;
1163 let region = LogicalViewportRegion::new(LogicalScreenPosition::from_vec2(minimum), viewport)
1164 .map_err(|_| GlyphError::InvalidGlyph)?;
1165 Ok(GlyphRunBounds {
1166 region: Some(region),
1167 })
1168}
1169
1170fn logical_region_arithmetic_is_finite(region: LogicalViewportRegion) -> bool {
1171 let origin = region.origin().to_vec2();
1172 let end = origin + region.viewport().size();
1173 origin.is_finite() && end.is_finite()
1174}
1175
1176#[cfg(test)]
1177mod tests {
1178 use super::*;
1179
1180 fn rectangle(x: u32) -> ImageTexelRect {
1181 ImageTexelRect::new(x, 0, 1, 1).unwrap()
1182 }
1183
1184 fn positioned(glyph: u32, x: f32) -> PositionedGlyph2d {
1185 PositionedGlyph2d::new(
1186 GlyphId::new(glyph),
1187 LogicalViewportRegion::new(
1188 LogicalScreenPosition::new(x, 2.0),
1189 LogicalViewport::new(4.0, 6.0).unwrap(),
1190 )
1191 .unwrap(),
1192 Color::WHITE,
1193 )
1194 .unwrap()
1195 }
1196
1197 #[test]
1198 fn atlas_entries_sort_and_reject_duplicate_or_out_of_bounds_glyphs() {
1199 let budget = GlyphAtlasBudget::default();
1200 let mut entries = vec![
1201 GlyphAtlasEntry::new(GlyphId::new(2), rectangle(1)),
1202 GlyphAtlasEntry::new(GlyphId::new(1), rectangle(0)),
1203 ];
1204 assert_eq!(validate_atlas_entries(&mut entries, 2, 1, budget), Ok(()));
1205 assert_eq!(entries[0].glyph(), GlyphId::new(1));
1206
1207 let mut duplicate = vec![
1208 GlyphAtlasEntry::new(GlyphId::new(7), rectangle(0)),
1209 GlyphAtlasEntry::new(GlyphId::new(7), rectangle(1)),
1210 ];
1211 assert_eq!(
1212 validate_atlas_entries(&mut duplicate, 2, 1, budget),
1213 Err(GlyphError::DuplicateGlyph {
1214 glyph: GlyphId::new(7)
1215 })
1216 );
1217
1218 let mut outside = vec![GlyphAtlasEntry::new(GlyphId::new(9), rectangle(2))];
1219 assert_eq!(
1220 validate_atlas_entries(&mut outside, 2, 1, budget),
1221 Err(GlyphError::InvalidGlyph)
1222 );
1223
1224 let mut overlapping = vec![
1225 GlyphAtlasEntry::new(GlyphId::new(10), ImageTexelRect::new(0, 0, 2, 2).unwrap()),
1226 GlyphAtlasEntry::new(GlyphId::new(11), ImageTexelRect::new(1, 1, 2, 2).unwrap()),
1227 ];
1228 assert_eq!(
1229 validate_atlas_entries(&mut overlapping, 4, 4, budget),
1230 Err(GlyphError::OverlappingGlyph {
1231 glyph: GlyphId::new(11),
1232 conflicting_glyph: GlyphId::new(10),
1233 })
1234 );
1235 }
1236
1237 #[test]
1238 fn incremental_glyph_overlap_is_rejected_before_metadata_or_pixel_update() {
1239 let entries = [GlyphAtlasEntry::new(
1240 GlyphId::new(1),
1241 ImageTexelRect::new(0, 0, 4, 4).unwrap(),
1242 )];
1243 let overlapping =
1244 GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(3, 0, 4, 4).unwrap());
1245 assert_eq!(
1246 validate_glyph_insertion(&entries, overlapping),
1247 Err(GlyphError::OverlappingGlyph {
1248 glyph: GlyphId::new(2),
1249 conflicting_glyph: GlyphId::new(1),
1250 })
1251 );
1252 assert_eq!(entries.len(), 1);
1253
1254 let adjacent =
1255 GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(4, 0, 4, 4).unwrap());
1256 assert_eq!(validate_glyph_insertion(&entries, adjacent), Ok(Some(1)));
1257
1258 let below = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 8, 4, 4).unwrap());
1259 assert_eq!(validate_glyph_insertion(&entries, below), Ok(Some(1)));
1260
1261 let entries_below = [GlyphAtlasEntry::new(
1262 GlyphId::new(1),
1263 ImageTexelRect::new(0, 8, 4, 4).unwrap(),
1264 )];
1265 let above = GlyphAtlasEntry::new(GlyphId::new(2), ImageTexelRect::new(0, 0, 4, 4).unwrap());
1266 assert_eq!(validate_glyph_insertion(&entries_below, above), Ok(Some(1)));
1267 }
1268
1269 #[test]
1270 fn default_maximum_non_overlapping_atlas_validation_is_subquadratic() {
1271 let mut entries = Vec::with_capacity(65_536);
1272 for glyph in 0..65_536_u32 {
1273 entries.push(GlyphAtlasEntry::new(
1274 GlyphId::new(glyph),
1275 ImageTexelRect::new(glyph % 256, glyph / 256, 1, 1).unwrap(),
1276 ));
1277 }
1278 assert_eq!(
1279 validate_atlas_entries(&mut entries, 256, 256, GlyphAtlasBudget::default()),
1280 Ok(())
1281 );
1282 }
1283
1284 #[test]
1285 fn positioned_run_resolves_opaque_scientific_glyphs_and_measures_bounds() {
1286 let entries = [
1287 GlyphAtlasEntry::new(GlyphId::new('Δ' as u32), rectangle(1)),
1288 GlyphAtlasEntry::new(GlyphId::new('μ' as u32), rectangle(0)),
1289 GlyphAtlasEntry::new(GlyphId::new('∫' as u32), rectangle(2)),
1290 ];
1291 let glyphs = [
1292 positioned('μ' as u32, 1.0),
1293 positioned('Δ' as u32, 5.0),
1294 positioned('∫' as u32, 9.0),
1295 ];
1296 assert_eq!(resolve_glyph_sprites(&entries, &glyphs).unwrap().len(), 3);
1297 let bounds = measure_glyphs(&glyphs).unwrap().region().unwrap();
1298 assert_eq!(bounds.origin(), LogicalScreenPosition::new(1.0, 2.0));
1299 assert_eq!(bounds.viewport().size(), Vec2::new(12.0, 6.0));
1300
1301 let missing = [positioned('Σ' as u32, 1.0)];
1302 assert_eq!(
1303 resolve_glyph_sprites(&entries, &missing),
1304 Err(GlyphError::MissingGlyph {
1305 glyph: GlyphId::new('Σ' as u32),
1306 index: 0,
1307 })
1308 );
1309 }
1310
1311 #[test]
1312 fn glyph_run_recovery_rejects_forked_atlas_mapping() {
1313 let glyph = positioned(42, 1.0);
1314 let left = rectangle(0);
1315 let right = rectangle(1);
1316 let source_entries = [GlyphAtlasEntry::new(GlyphId::new(42), left)];
1317 let forked_entries = [GlyphAtlasEntry::new(GlyphId::new(42), right)];
1318 let source_sprites = [ImageSprite2d::new(left, glyph.destination(), glyph.tint()).unwrap()];
1319
1320 assert_eq!(
1321 validate_glyph_run_sources(&source_entries, &[glyph], &source_sprites),
1322 Ok(())
1323 );
1324 assert_eq!(
1325 validate_glyph_run_sources(&forked_entries, &[glyph], &source_sprites),
1326 Err(GlyphError::Image(ImageError::RecoverySourceMismatch))
1327 );
1328 }
1329}