Reintroduce damage tracking for `iced_tiny_skia`

10 files changed, 347 insertions, 92 deletions

diff --git a/graphics/src/damage.rs b/graphics/src/damage.rs
new file mode 100644
index 00000000..ff8edaf5
--- /dev/null
+++ b/graphics/src/damage.rs
@@ -0,0 +1,80 @@
+//! Compute the damage between frames.
+use crate::core::Rectangle;
+
+/// Diffs the damage regions given some previous and current primitives.
+pub fn diff<T>(
+    previous: &[T],
+    current: &[T],
+    bounds: impl Fn(&T) -> Vec<Rectangle>,
+    diff: impl Fn(&T, &T) -> Vec<Rectangle>,
+) -> Vec<Rectangle> {
+    let damage = previous.iter().zip(current).flat_map(|(a, b)| diff(a, b));
+
+    if previous.len() == current.len() {
+        damage.collect()
+    } else {
+        let (smaller, bigger) = if previous.len() < current.len() {
+            (previous, current)
+        } else {
+            (current, previous)
+        };
+
+        // Extend damage by the added/removed primitives
+        damage
+            .chain(bigger[smaller.len()..].iter().flat_map(bounds))
+            .collect()
+    }
+}
+
+/// Computes the damage regions given some previous and current primitives.
+pub fn list<T>(
+    previous: &[T],
+    current: &[T],
+    bounds: impl Fn(&T) -> Vec<Rectangle>,
+    are_equal: impl Fn(&T, &T) -> bool,
+) -> Vec<Rectangle> {
+    diff(previous, current, &bounds, |a, b| {
+        if are_equal(a, b) {
+            vec![]
+        } else {
+            bounds(a).into_iter().chain(bounds(b)).collect()
+        }
+    })
+}
+
+/// Groups the given damage regions that are close together inside the given
+/// bounds.
+pub fn group(mut damage: Vec<Rectangle>, bounds: Rectangle) -> Vec<Rectangle> {
+    use std::cmp::Ordering;
+
+    const AREA_THRESHOLD: f32 = 20_000.0;
+
+    damage.sort_by(|a, b| {
+        a.x.partial_cmp(&b.x)
+            .unwrap_or(Ordering::Equal)
+            .then_with(|| a.y.partial_cmp(&b.y).unwrap_or(Ordering::Equal))
+    });
+
+    let mut output = Vec::new();
+    let mut scaled = damage
+        .into_iter()
+        .filter_map(|region| region.intersection(&bounds))
+        .filter(|region| region.width >= 1.0 && region.height >= 1.0);
+
+    if let Some(mut current) = scaled.next() {
+        for region in scaled {
+            let union = current.union(&region);
+
+            if union.area() - current.area() - region.area() <= AREA_THRESHOLD {
+                current = union;
+            } else {
+                output.push(current);
+                current = region;
+            }
+        }
+
+        output.push(current);
+    }
+
+    output
+}
diff --git a/graphics/src/layer.rs b/graphics/src/layer.rs
index 0187cc59..c9a818fb 100644
--- a/graphics/src/layer.rs
+++ b/graphics/src/layer.rs
@@ -113,6 +113,11 @@ impl<T: Layer> Stack<T> {
         self.layers[..self.active_count].iter()
     }
 
+    /// Returns the slice of layers in the [`Stack`].
+    pub fn as_slice(&self) -> &[T] {
+        &self.layers[..self.active_count]
+    }
+
     /// Flushes and settles any primitives in the current layer of the [`Stack`].
     pub fn flush(&mut self) {
         self.layers[self.current].flush();
diff --git a/graphics/src/lib.rs b/graphics/src/lib.rs
index a9649c6e..865ebd97 100644
--- a/graphics/src/lib.rs
+++ b/graphics/src/lib.rs
@@ -15,6 +15,7 @@ mod viewport;
 
 pub mod color;
 pub mod compositor;
+pub mod damage;
 pub mod error;
 pub mod gradient;
 pub mod image;
diff --git a/graphics/src/text.rs b/graphics/src/text.rs
index c204c850..31b6de28 100644
--- a/graphics/src/text.rs
+++ b/graphics/src/text.rs
@@ -70,6 +70,76 @@ pub enum Text {
     },
 }
 
+impl Text {
+    /// Returns the visible bounds of the [`Text`].
+    pub fn visible_bounds(&self) -> Option<Rectangle> {
+        let (bounds, horizontal_alignment, vertical_alignment) = match self {
+            Text::Paragraph {
+                position,
+                paragraph,
+                clip_bounds,
+                ..
+            } => (
+                Rectangle::new(*position, paragraph.min_bounds)
+                    .intersection(clip_bounds),
+                Some(paragraph.horizontal_alignment),
+                Some(paragraph.vertical_alignment),
+            ),
+            Text::Editor {
+                editor,
+                position,
+                clip_bounds,
+                ..
+            } => (
+                Rectangle::new(*position, editor.bounds)
+                    .intersection(clip_bounds),
+                None,
+                None,
+            ),
+            Text::Cached {
+                bounds,
+                clip_bounds,
+                horizontal_alignment,
+                vertical_alignment,
+                ..
+            } => (
+                bounds.intersection(clip_bounds),
+                Some(*horizontal_alignment),
+                Some(*vertical_alignment),
+            ),
+            Text::Raw { raw, .. } => (Some(raw.clip_bounds), None, None),
+        };
+
+        let mut bounds = bounds?;
+
+        if let Some(alignment) = horizontal_alignment {
+            match alignment {
+                alignment::Horizontal::Left => {}
+                alignment::Horizontal::Center => {
+                    bounds.x -= bounds.width / 2.0;
+                }
+                alignment::Horizontal::Right => {
+                    bounds.x -= bounds.width;
+                }
+            }
+        }
+
+        if let Some(alignment) = vertical_alignment {
+            match alignment {
+                alignment::Vertical::Top => {}
+                alignment::Vertical::Center => {
+                    bounds.y -= bounds.height / 2.0;
+                }
+                alignment::Vertical::Bottom => {
+                    bounds.y -= bounds.height;
+                }
+            }
+        }
+
+        Some(bounds)
+    }
+}
+
 /// The regular variant of the [Fira Sans] font.
 ///
 /// It is loaded as part of the default fonts in Wasm builds.
diff --git a/tiny_skia/src/engine.rs b/tiny_skia/src/engine.rs
index 3930f46a..fbca1274 100644
--- a/tiny_skia/src/engine.rs
+++ b/tiny_skia/src/engine.rs
@@ -402,9 +402,9 @@ impl Engine {
                 horizontal_alignment,
                 vertical_alignment,
                 shaping,
-                clip_bounds: _, // TODO
+                clip_bounds: text_bounds, // TODO
             } => {
-                let physical_bounds = *bounds * transformation;
+                let physical_bounds = *text_bounds * transformation;
 
                 if !clip_bounds.intersects(&physical_bounds) {
                     return;
@@ -539,10 +539,10 @@ impl Engine {
     pub fn draw_image(
         &mut self,
         image: &Image,
-        transformation: Transformation,
-        pixels: &mut tiny_skia::PixmapMut<'_>,
-        clip_mask: &mut tiny_skia::Mask,
-        clip_bounds: Rectangle,
+        _transformation: Transformation,
+        _pixels: &mut tiny_skia::PixmapMut<'_>,
+        _clip_mask: &mut tiny_skia::Mask,
+        _clip_bounds: Rectangle,
     ) {
         match image {
             #[cfg(feature = "image")]
@@ -551,21 +551,21 @@ impl Engine {
                 filter_method,
                 bounds,
             } => {
-                let physical_bounds = *bounds * transformation;
+                let physical_bounds = *bounds * _transformation;
 
-                if !clip_bounds.intersects(&physical_bounds) {
+                if !_clip_bounds.intersects(&physical_bounds) {
                     return;
                 }
 
-                let clip_mask = (!physical_bounds.is_within(&clip_bounds))
-                    .then_some(clip_mask as &_);
+                let clip_mask = (!physical_bounds.is_within(&_clip_bounds))
+                    .then_some(_clip_mask as &_);
 
                 self.raster_pipeline.draw(
                     handle,
                     *filter_method,
                     *bounds,
-                    pixels,
-                    into_transform(transformation),
+                    _pixels,
+                    into_transform(_transformation),
                     clip_mask,
                 );
             }
@@ -575,20 +575,20 @@ impl Engine {
                 color,
                 bounds,
             } => {
-                let physical_bounds = *bounds * transformation;
+                let physical_bounds = *bounds * _transformation;
 
-                if !clip_bounds.intersects(&physical_bounds) {
+                if !_clip_bounds.intersects(&physical_bounds) {
                     return;
                 }
 
-                let clip_mask = (!physical_bounds.is_within(&clip_bounds))
-                    .then_some(clip_mask as &_);
+                let clip_mask = (!physical_bounds.is_within(&_clip_bounds))
+                    .then_some(_clip_mask as &_);
 
                 self.vector_pipeline.draw(
                     handle,
                     *color,
                     physical_bounds,
-                    pixels,
+                    _pixels,
                     clip_mask,
                 );
             }
diff --git a/tiny_skia/src/geometry.rs b/tiny_skia/src/geometry.rs
index 04aabf0d..117daf41 100644
--- a/tiny_skia/src/geometry.rs
+++ b/tiny_skia/src/geometry.rs
@@ -166,7 +166,7 @@ impl geometry::frame::Backend for Frame {
 
         let (scale_x, scale_y) = self.transform.get_scale();
 
-        if self.transform.is_scale_translate()
+        if !self.transform.has_skew()
             && scale_x == scale_y
             && scale_x > 0.0
             && scale_y > 0.0
diff --git a/tiny_skia/src/layer.rs b/tiny_skia/src/layer.rs
index 1f5c8b46..0d770d81 100644
--- a/tiny_skia/src/layer.rs
+++ b/tiny_skia/src/layer.rs
@@ -2,6 +2,7 @@ use crate::core::image;
 use crate::core::renderer::Quad;
 use crate::core::svg;
 use crate::core::{Background, Color, Point, Rectangle, Transformation};
+use crate::graphics::damage;
 use crate::graphics::layer;
 use crate::graphics::text::{Editor, Paragraph, Text};
 use crate::graphics::{self, Image};
@@ -20,39 +21,6 @@ pub struct Layer {
     pub images: Vec<Image>,
 }
 
-#[derive(Debug, Clone)]
-pub enum Item<T> {
-    Live(T),
-    Group(Vec<T>, Rectangle, Transformation),
-    Cached(Rc<[T]>, Rectangle, Transformation),
-}
-
-impl<T> Item<T> {
-    pub fn transformation(&self) -> Transformation {
-        match self {
-            Item::Live(_) => Transformation::IDENTITY,
-            Item::Group(_, _, transformation)
-            | Item::Cached(_, _, transformation) => *transformation,
-        }
-    }
-
-    pub fn clip_bounds(&self) -> Rectangle {
-        match self {
-            Item::Live(_) => Rectangle::INFINITE,
-            Item::Group(_, clip_bounds, _)
-            | Item::Cached(_, clip_bounds, _) => *clip_bounds,
-        }
-    }
-
-    pub fn as_slice(&self) -> &[T] {
-        match self {
-            Item::Live(item) => std::slice::from_ref(item),
-            Item::Group(group, _, _) => group.as_slice(),
-            Item::Cached(cache, _, _) => cache,
-        }
-    }
-}
-
 impl Layer {
     pub fn draw_quad(
         &mut self,
@@ -204,6 +172,81 @@ impl Layer {
             transformation,
         ));
     }
+
+    pub fn damage(previous: &Self, current: &Self) -> Vec<Rectangle> {
+        let mut damage = damage::list(
+            &previous.quads,
+            &current.quads,
+            |(quad, _)| vec![quad.bounds.expand(1.0)],
+            |(quad_a, background_a), (quad_b, background_b)| {
+                quad_a == quad_b && background_a == background_b
+            },
+        );
+
+        let text = damage::diff(
+            &previous.text,
+            &current.text,
+            |item| {
+                item.as_slice()
+                    .iter()
+                    .filter_map(Text::visible_bounds)
+                    .map(|bounds| bounds * item.transformation())
+                    .collect()
+            },
+            |text_a, text_b| {
+                damage::list(
+                    text_a.as_slice(),
+                    text_b.as_slice(),
+                    |text| {
+                        text.visible_bounds()
+                            .into_iter()
+                            .filter_map(|bounds| {
+                                bounds.intersection(&text_a.clip_bounds())
+                            })
+                            .collect()
+                    },
+                    |text_a, text_b| text_a == text_b,
+                )
+            },
+        );
+
+        let primitives = damage::list(
+            &previous.primitives,
+            &current.primitives,
+            |item| match item {
+                Item::Live(primitive) => vec![primitive.visible_bounds()],
+                Item::Group(primitives, bounds, transformation) => {
+                    damage::group(
+                        primitives
+                            .as_slice()
+                            .iter()
+                            .map(Primitive::visible_bounds)
+                            .map(|bounds| bounds * *transformation)
+                            .collect(),
+                        *bounds,
+                    )
+                }
+                Item::Cached(_, bounds, _) => {
+                    vec![*bounds]
+                }
+            },
+            |primitive_a, primitive_b| match (primitive_a, primitive_b) {
+                (
+                    Item::Cached(cache_a, bounds_a, transformation_a),
+                    Item::Cached(cache_b, bounds_b, transformation_b),
+                ) => {
+                    Rc::ptr_eq(cache_a, cache_b)
+                        && bounds_a == bounds_b
+                        && transformation_a == transformation_b
+                }
+                _ => false,
+            },
+        );
+
+        damage.extend(text);
+        damage.extend(primitives);
+        damage
+    }
 }
 
 impl Default for Layer {
@@ -236,8 +279,41 @@ impl graphics::Layer for Layer {
         self.bounds = Rectangle::INFINITE;
 
         self.quads.clear();
-        self.text.clear();
         self.primitives.clear();
+        self.text.clear();
         self.images.clear();
     }
 }
+
+#[derive(Debug, Clone)]
+pub enum Item<T> {
+    Live(T),
+    Group(Vec<T>, Rectangle, Transformation),
+    Cached(Rc<[T]>, Rectangle, Transformation),
+}
+
+impl<T> Item<T> {
+    pub fn transformation(&self) -> Transformation {
+        match self {
+            Item::Live(_) => Transformation::IDENTITY,
+            Item::Group(_, _, transformation)
+            | Item::Cached(_, _, transformation) => *transformation,
+        }
+    }
+
+    pub fn clip_bounds(&self) -> Rectangle {
+        match self {
+            Item::Live(_) => Rectangle::INFINITE,
+            Item::Group(_, clip_bounds, _)
+            | Item::Cached(_, clip_bounds, _) => *clip_bounds,
+        }
+    }
+
+    pub fn as_slice(&self) -> &[T] {
+        match self {
+            Item::Live(item) => std::slice::from_ref(item),
+            Item::Group(group, _, _) => group.as_slice(),
+            Item::Cached(cache, _, _) => cache,
+        }
+    }
+}
diff --git a/tiny_skia/src/lib.rs b/tiny_skia/src/lib.rs
index fed2f32c..4c2c9430 100644
--- a/tiny_skia/src/lib.rs
+++ b/tiny_skia/src/lib.rs
@@ -29,7 +29,7 @@ pub use geometry::Geometry;
 
 use crate::core::renderer;
 use crate::core::{
-    Background, Color, Font, Pixels, Point, Rectangle, Size, Transformation,
+    Background, Color, Font, Pixels, Point, Rectangle, Transformation,
 };
 use crate::engine::Engine;
 use crate::graphics::compositor;
@@ -58,9 +58,9 @@ impl Renderer {
         }
     }
 
-    pub fn layers(&mut self) -> impl Iterator<Item = &Layer> {
+    pub fn layers(&mut self) -> &[Layer] {
         self.layers.flush();
-        self.layers.iter()
+        self.layers.as_slice()
     }
 
     pub fn draw<T: AsRef<str>>(
@@ -135,12 +135,12 @@ impl Renderer {
             );
 
             for layer in self.layers.iter() {
-                let Some(clip_bounds) = region.intersection(&layer.bounds)
+                let Some(clip_bounds) =
+                    region.intersection(&(layer.bounds * scale_factor))
                 else {
                     continue;
                 };
 
-                let clip_bounds = clip_bounds * scale_factor;
                 engine::adjust_clip_mask(clip_mask, clip_bounds);
 
                 for (quad, background) in &layer.quads {
@@ -154,30 +154,15 @@ impl Renderer {
                     );
                 }
 
-                for group in &layer.text {
-                    for text in group.as_slice() {
-                        self.engine.draw_text(
-                            text,
-                            group.transformation()
-                                * Transformation::scale(scale_factor),
-                            pixels,
-                            clip_mask,
-                            clip_bounds,
-                        );
-                    }
-                }
-
                 for group in &layer.primitives {
-                    let Some(new_clip_bounds) =
-                        group.clip_bounds().intersection(&layer.bounds)
+                    let Some(new_clip_bounds) = (group.clip_bounds()
+                        * scale_factor)
+                        .intersection(&clip_bounds)
                     else {
                         continue;
                     };
 
-                    engine::adjust_clip_mask(
-                        clip_mask,
-                        new_clip_bounds * scale_factor,
-                    );
+                    engine::adjust_clip_mask(clip_mask, new_clip_bounds);
 
                     for primitive in group.as_slice() {
                         self.engine.draw_primitive(
@@ -193,6 +178,19 @@ impl Renderer {
                     engine::adjust_clip_mask(clip_mask, clip_bounds);
                 }
 
+                for group in &layer.text {
+                    for text in group.as_slice() {
+                        self.engine.draw_text(
+                            text,
+                            group.transformation()
+                                * Transformation::scale(scale_factor),
+                            pixels,
+                            clip_mask,
+                            clip_bounds,
+                        );
+                    }
+                }
+
                 for image in &layer.images {
                     self.engine.draw_image(
                         image,
@@ -370,7 +368,7 @@ impl graphics::mesh::Renderer for Renderer {
 impl core::image::Renderer for Renderer {
     type Handle = core::image::Handle;
 
-    fn measure_image(&self, handle: &Self::Handle) -> Size<u32> {
+    fn measure_image(&self, handle: &Self::Handle) -> crate::core::Size<u32> {
         self.engine.raster_pipeline.dimensions(handle)
     }
 
@@ -387,7 +385,10 @@ impl core::image::Renderer for Renderer {
 
 #[cfg(feature = "svg")]
 impl core::svg::Renderer for Renderer {
-    fn measure_svg(&self, handle: &core::svg::Handle) -> Size<u32> {
+    fn measure_svg(
+        &self,
+        handle: &core::svg::Handle,
+    ) -> crate::core::Size<u32> {
         self.engine.vector_pipeline.viewport_dimensions(handle)
     }
 
diff --git a/tiny_skia/src/primitive.rs b/tiny_skia/src/primitive.rs
index 5305788d..5de51047 100644
--- a/tiny_skia/src/primitive.rs
+++ b/tiny_skia/src/primitive.rs
@@ -1,3 +1,5 @@
+use crate::core::Rectangle;
+
 #[derive(Debug, Clone, PartialEq)]
 pub enum Primitive {
     /// A path filled with some paint.
@@ -19,3 +21,20 @@ pub enum Primitive {
         stroke: tiny_skia::Stroke,
     },
 }
+
+impl Primitive {
+    /// Returns the visible bounds of the [`Primitive`].
+    pub fn visible_bounds(&self) -> Rectangle {
+        let bounds = match self {
+            Primitive::Fill { path, .. } => path.bounds(),
+            Primitive::Stroke { path, .. } => path.bounds(),
+        };
+
+        Rectangle {
+            x: bounds.x(),
+            y: bounds.y(),
+            width: bounds.width(),
+            height: bounds.height(),
+        }
+    }
+}
diff --git a/tiny_skia/src/window/compositor.rs b/tiny_skia/src/window/compositor.rs
index e1a9dfec..153af6d5 100644
--- a/tiny_skia/src/window/compositor.rs
+++ b/tiny_skia/src/window/compositor.rs
@@ -1,5 +1,6 @@
 use crate::core::{Color, Rectangle, Size};
 use crate::graphics::compositor::{self, Information};
+use crate::graphics::damage;
 use crate::graphics::error::{self, Error};
 use crate::graphics::{self, Viewport};
 use crate::{Layer, Renderer, Settings};
@@ -154,7 +155,7 @@ pub fn present<T: AsRef<str>>(
         .buffer_mut()
         .map_err(|_| compositor::SurfaceError::Lost)?;
 
-    let _last_layers = {
+    let last_layers = {
         let age = buffer.age();
 
         surface.max_age = surface.max_age.max(age);
@@ -167,26 +168,28 @@ pub fn present<T: AsRef<str>>(
         }
     };
 
-    // TODO
-    // let damage = last_layers
-    //     .and_then(|last_layers| {
-    //         (surface.background_color == background_color)
-    //             .then(|| damage::layers(last_layers, renderer.layers()))
-    //     })
-    //     .unwrap_or_else(|| vec![Rectangle::with_size(viewport.logical_size())]);
-
-    let damage = vec![Rectangle::with_size(viewport.logical_size())];
+    let damage = last_layers
+        .and_then(|last_layers| {
+            (surface.background_color == background_color).then(|| {
+                damage::diff(
+                    last_layers,
+                    renderer.layers(),
+                    |layer| vec![layer.bounds],
+                    Layer::damage,
+                )
+            })
+        })
+        .unwrap_or_else(|| vec![Rectangle::with_size(viewport.logical_size())]);
 
     if damage.is_empty() {
         return Ok(());
     }
 
-    surface
-        .layer_stack
-        .push_front(renderer.layers().cloned().collect());
+    surface.layer_stack.push_front(renderer.layers().to_vec());
     surface.background_color = background_color;
 
-    // let damage = damage::group(damage, viewport.logical_size());
+    let damage =
+        damage::group(damage, Rectangle::with_size(viewport.logical_size()));
 
     let mut pixels = tiny_skia::PixmapMut::from_bytes(
         bytemuck::cast_slice_mut(&mut buffer),