Render: find a glyph's line by bisection for gradient and WordArt text

crates/render/src/text_draw.rs

@@ -105,6 +105,7 @@ pub fn draw_layout(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout, tr:
 pub fn draw_layout_with(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout, tr: Rect, m: Affine, paras: &[(usize, ParaState)]) {
     let para = |i: usize| paras.iter().find(|(p, _)| *p == i).map(|(_, s)| *s).unwrap_or_default();
     let m = text_transform(m, tr, l.rotation);
+    let lines_of = LineIndex::new(l);
     let deco = |ctx: &mut RenderContext, d: &deckcraft_text::Deco| {
         let ps = para(d.para);
         if !ps.visible || ps.opacity <= 0.001 {
@@ -144,7 +145,7 @@ pub fn draw_layout_with(ctx: &mut RenderContext, l: &deckcraft_text::TextLayout,
                 draw_glyph(ctx, run, *gid, at, ps.opacity);
                 continue;
             };
-            let li = line_at(l, run.para, *y);
+            let li = lines_of.line_at(run.para, *y);
             if !grads.iter().any(|(i, _)| *i == li) {
                 let scheme = deckcraft_color::ColorScheme { name: String::new(), colors: [Rgba::BLACK; 12] };
                 let stops = g.stops.iter().map(|s| (s.pos, s.color.resolve(&scheme, None))).collect();
@@ -191,8 +192,78 @@ pub(crate) fn fill_deco(ctx: &mut RenderContext, d: &deckcraft_text::Deco) {
     }
 }
 
-/// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline).
-fn line_at(l: &deckcraft_text::TextLayout, para: usize, y: f64) -> usize {
+/// Finds the line of a paragraph holding a glyph on baseline `y` without scanning the paragraph's
+/// lines for every glyph. A paragraph whose lines are ordered top to bottom (every layout the text
+/// crate produces) is searched by bisection; any other falls back to a scan with the same answer.
+pub(crate) struct LineIndex<'a> {
+    l: &'a deckcraft_text::TextLayout,
+    /// Per paragraph: its lines' tops, bottoms and baselines all rise with the line index.
+    ordered: Vec<bool>,
+}
+
+impl<'a> LineIndex<'a> {
+    pub(crate) fn new(l: &'a deckcraft_text::TextLayout) -> Self {
+        let ordered = l
+            .para_lines
+            .iter()
+            .map(|&(first, count)| {
+                let end = first.saturating_add(count).min(l.lines.len());
+                l.lines.get(first..end).is_some_and(|ls| {
+                    ls.iter().all(|a| a.top <= a.bottom)
+                        && ls.windows(2).all(|w| w[0].top <= w[1].top && w[0].bottom <= w[1].bottom && w[0].baseline <= w[1].baseline)
+                })
+            })
+            .collect();
+        LineIndex { l, ordered }
+    }
+
+    /// The nearest line baseline to `y` among `lines` (the first of equals), as an index into `lines`.
+    fn nearest(lines: &[deckcraft_text::LineInfo], y: f64) -> Option<usize> {
+        let i = lines.partition_point(|li| li.baseline < y);
+        let best = match (i.checked_sub(1), lines.get(i)) {
+            (Some(p), Some(n)) => {
+                if (lines[p].baseline - y).abs() <= (n.baseline - y).abs() {
+                    p
+                } else {
+                    i
+                }
+            }
+            (Some(p), None) => p,
+            (None, Some(_)) => i,
+            (None, None) => return None,
+        };
+        let b = lines[best].baseline;
+        Some(lines.partition_point(|li| li.baseline < b))
+    }
+
+    /// The paragraph's lines when they are ordered, with the index of the first.
+    fn ordered_lines(&self, para: usize) -> Option<(usize, &[deckcraft_text::LineInfo])> {
+        let &(first, count) = self.l.para_lines.get(para)?;
+        let end = first.saturating_add(count).min(self.l.lines.len());
+        (self.ordered[para] && first < end).then(|| (first, &self.l.lines[first..end]))
+    }
+
+    /// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline).
+    pub(crate) fn line_at(&self, para: usize, y: f64) -> usize {
+        if let Some((first, ls)) = self.ordered_lines(para) {
+            return Self::nearest(ls, y).map_or(0, |i| first + i);
+        }
+        line_at_scan(self.l, para, y)
+    }
+
+    /// The first line of paragraph `para` whose box holds `y`, else the nearest baseline's line.
+    pub(crate) fn line_of(&self, para: usize, y: f64) -> Option<usize> {
+        let Some((first, ls)) = self.ordered_lines(para) else { return crate::warp::line_of_scan(self.l, para, y) };
+        let i = ls.partition_point(|li| li.bottom + 0.01 < y);
+        if ls.get(i).is_some_and(|li| y >= li.top - 0.01) {
+            return Some(first + i);
+        }
+        Self::nearest(ls, y).map(|i| first + i)
+    }
+}
+
+/// The line of paragraph `para` holding a glyph on baseline `y` (the nearest baseline), by scanning.
+fn line_at_scan(l: &deckcraft_text::TextLayout, para: usize, y: f64) -> usize {
     if let Some(&(first, count)) = l.para_lines.get(para) {
         if count == 0 {
             return 0;
@@ -318,3 +389,38 @@ fn draw_glyph_with(
         ctx.stroke_path(&path);
     }
 }
+
+#[cfg(test)]
+mod line_index_tests {
+    use super::*;
+    use deckcraft_text::{LineInfo, TextLayout};
+
+    fn layout(ordered: bool) -> TextLayout {
+        let line = |para, top: f64| LineInfo { para, top, baseline: top + 8.0, bottom: top + 10.0, ..Default::default() };
+        let mut lines: Vec<LineInfo> = (0..40).map(|i| line(usize::from(i >= 25), f64::from(i) * 10.0)).collect();
+        if !ordered {
+            lines.swap(3, 7);
+        }
+        TextLayout { lines, para_lines: vec![(0, 25), (25, 15)], ..Default::default() }
+    }
+
+    #[test]
+    fn bisection_matches_the_scan() {
+        for ordered in [true, false] {
+            let l = layout(ordered);
+            let idx = LineIndex::new(l_ref(&l));
+            assert_eq!(idx.ordered, vec![ordered, true]);
+            for para in 0..2 {
+                for k in -20..450 {
+                    let y = f64::from(k) * 0.9;
+                    assert_eq!(idx.line_at(para, y), line_at_scan(&l, para, y), "line_at {para} {y}");
+                    assert_eq!(idx.line_of(para, y), crate::warp::line_of_scan(&l, para, y), "line_of {para} {y}");
+                }
+            }
+        }
+    }
+
+    fn l_ref(l: &TextLayout) -> &TextLayout {
+        l
+    }
+}

crates/render/src/warp.rs

@@ -9,13 +9,14 @@ use deckcraft_text::{GlyphRun, TextLayout};
 use kurbo::{Affine, BezPath, PathEl, Point, Rect, Shape as _};
 use vello_cpu::{RenderContext, peniko};
 
+use crate::text_draw::LineIndex;
 use crate::{ParaState, color, glyph, scale_of, text_transform};
 
 /// Most points one warped glyph may have (a hostile size or zoom can't explode the work).
 const MAX_POINTS: usize = 40_000;
 
-/// The line of `l` a glyph of paragraph `para` on baseline `y` belongs to.
-fn line_of(l: &TextLayout, para: usize, y: f64) -> Option<usize> {
+/// The line of `l` a glyph of paragraph `para` on baseline `y` belongs to, by scanning.
+pub(crate) fn line_of_scan(l: &TextLayout, para: usize, y: f64) -> Option<usize> {
     if let Some(&(first, count)) = l.para_lines.get(para) {
         if count == 0 {
             return None;
@@ -110,6 +111,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
     let para = |i: usize| paras.iter().find(|(p, _)| *p == i).map(|(_, s)| *s).unwrap_or_default();
     let m = text_transform(m, tr, l.rotation);
     let n = l.lines.len();
+    let lines_of = LineIndex::new(l);
     let mut ink: Vec<Option<Rect>> = vec![None; n];
     let mut off: Vec<Option<f64>> = vec![None; n];
     let mut items: Vec<Item> = Vec::new();
@@ -117,7 +119,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
         let k = run.size / run.face.upem.max(1.0);
         let skew = if run.fake_italic { Affine::new([1.0, 0.0, -0.2, 1.0, 0.0, 0.0]) } else { Affine::IDENTITY };
         for (gid, x, y) in &run.glyphs {
-            let Some(li) = line_of(l, run.para, *y) else { continue };
+            let Some(li) = lines_of.line_of(run.para, *y) else { continue };
             if let Some(o) = off.get_mut(li) {
                 *o = Some(o.map_or(ref_offset(run), |v| v.max(ref_offset(run))));
             }
@@ -156,7 +158,7 @@ pub(crate) fn draw(ctx: &mut RenderContext, l: &TextLayout, tr: Rect, m: Affine,
             return;
         }
         let y = (d.rect.y0 + d.rect.y1) / 2.0;
-        let Some(li) = line_of(l, d.para, y) else { return };
+        let Some(li) = lines_of.line_of(d.para, y) else { return };
         ctx.set_transform(m * Affine::translate(ps.offset));
         ctx.set_paint(color(d.color, ps.opacity));
         for r in d.pieces() {