damage.rs
raw
//! Damage tracking for incremental software rendering.
//!
//! The backend remembers, per fragment, what it drew last frame — the
//! fragment's store epoch, the device transform and clip context it was
//! encountered under, and its exact device-space bounds. Each render runs a
//! cheap geometry prepass over the fragment tree; anything whose (epoch,
//! transform, clip) still match reuses its recorded bounds, anything else
//! recomputes them and contributes damage (old bounds ∪ new bounds).
//! Removed fragments contribute their old bounds. The draw pass then
//! repaints into a full-viewport scratch pixmap with exactly the draw calls
//! a full render would make for content touching the damage — bit-identical
//! by construction — and copies the damaged rects back, skipping subtrees
//! whose bounds miss every rect.
//!
//! Correctness rests on two properties: damage is a superset of every pixel
//! that can differ from the previous frame (bounds are exact or
//! conservatively larger, and epoch bumps on every mutable access), and the
//! draw pass repaints *everything* that intersects each damaged rect, in
//! paint order. Anything the prepass cannot vouch for — a fragment
//! referenced from two places, a changed viewport, a different store —
//! falls back to a full frame, which is exactly the pre-damage behavior.
use std::collections::HashMap;
use guiduck_scene::geom::{Affine, Rect};
use guiduck_scene::paint::Color;
use guiduck_scene::{DisplayItem, FragmentId, FragmentStore, RenderError, ScopeTracker};
use crate::MAX_DEPTH;
use crate::glyph::GlyphCache;
/// More damage rectangles than this collapse into their bounding box.
const MAX_DAMAGE_RECTS: usize = 16;
/// Damage covering at least this fraction of the viewport renders as a full
/// frame; the mask machinery would only add overhead.
const FULL_FRACTION: f64 = 0.9;
/// What the draw pass must repaint this frame.
pub enum Damage {
/// Everything — exactly the pre-damage behavior, no base mask.
Full,
/// Only these device-space pixel rectangles (possibly none: the
/// persistent pixmap is already correct).
Partial(Vec<Rect>),
}
/// What the backend drew for one fragment on the previous frame.
struct Record {
epoch: u64,
/// Device transform the fragment was encountered under.
transform: Affine,
/// Device-space bbox of the clip context open at the fragment's `Child`
/// site; `None` when unclipped.
clip: Option<Rect>,
/// Device bounds of the fragment's own leaf items (clip applied).
own: Option<Rect>,
/// `own` unioned with every child's subtree bounds.
subtree: Option<Rect>,
/// Whether the display list has no `Child` items (an unchanged leaf can
/// skip its item walk entirely).
leaf: bool,
/// The prepass generation that last visited this record.
stamp: u64,
}
/// Per-backend damage state, persisting across frames.
#[derive(Default)]
pub struct DamageTracker {
records: HashMap<FragmentId, Record>,
store_id: Option<u64>,
root: Option<FragmentId>,
width: u32,
height: u32,
scale: f64,
base_color: Option<Color>,
/// The store's mutation counter after the last successful prepass; when
/// it has not advanced, nothing in the store changed and the prepass is
/// skipped entirely.
counter: Option<u64>,
stamp: u64,
}
impl DamageTracker {
/// Run the geometry prepass and decide what to repaint. Always updates
/// the per-fragment records, so the *next* frame can diff against this
/// one even when this frame is full.
#[allow(clippy::too_many_arguments)]
pub fn plan(
&mut self,
root: FragmentId,
store: &FragmentStore,
width: u32,
height: u32,
scale: f64,
base_color: Color,
glyphs: &mut GlyphCache,
) -> Result<Damage, RenderError> {
let full = self.store_id != Some(store.store_id())
|| self.root != Some(root)
|| self.width != width
|| self.height != height
|| self.scale != scale
|| self.base_color != Some(base_color);
if !full && self.counter == Some(store.mutation_counter()) {
// Not one fragment was touched since the last plan: no prepass,
// no damage, the persistent pixmap is already this frame.
return Ok(Damage::Partial(Vec::new()));
}
self.stamp += 1;
self.counter = None;
self.store_id = Some(store.store_id());
self.root = Some(root);
self.width = width;
self.height = height;
self.scale = scale;
self.base_color = Some(base_color);
let mut prepass = Prepass {
store,
glyphs,
records: &mut self.records,
stamp: self.stamp,
damage: Vec::new(),
dag: false,
};
if let Err(err) = prepass.fragment(root, Affine::scale(scale), None, 0) {
// Half-updated records cannot be trusted; start over next frame.
self.records.clear();
return Err(err);
}
let mut damage = prepass.damage;
let dag = prepass.dag;
self.counter = Some(store.mutation_counter());
// Records the prepass did not visit belong to removed fragments:
// their old pixels are damage, their records are done.
let stamp = self.stamp;
self.records.retain(|_, record| {
if record.stamp == stamp {
true
} else {
if let Some(bounds) = record.subtree {
damage.push(bounds);
}
false
}
});
if dag {
// A fragment referenced from two places: one record per id can't
// represent that, so the records are meaningless. Repaint fully
// and re-learn from scratch next frame.
self.records.clear();
return Ok(Damage::Full);
}
if full {
return Ok(Damage::Full);
}
// Pixel-align the damage: pad a pixel for anti-aliased edges and
// round outward, so the copy back from the scratch moves whole
// pixels.
let viewport = Rect::new(0.0, 0.0, f64::from(width), f64::from(height));
let mut rects: Vec<Rect> = Vec::new();
for rect in damage {
let rect = pad_round(rect);
let Some(rect) = intersect(rect, viewport) else {
continue;
};
if !rects.iter().any(|r| contains(*r, rect)) {
rects.retain(|r| !contains(rect, *r));
rects.push(rect);
}
}
if rects.len() > MAX_DAMAGE_RECTS {
let bbox = rects
.iter()
.copied()
.reduce(|a, b| a.union(b))
.expect("non-empty");
rects = vec![bbox];
}
let area: f64 = rects.iter().map(|r| r.area()).sum();
if area >= FULL_FRACTION * viewport.area() {
return Ok(Damage::Full);
}
Ok(Damage::Partial(rects))
}
/// Whether the fragment's subtree can touch the damaged region. Unknown
/// fragments answer yes — drawing too much is safe, skipping is not.
pub(crate) fn subtree_intersects(&self, id: FragmentId, rects: &[Rect]) -> bool {
match self.records.get(&id) {
Some(record) => bounds_intersect(record.subtree, rects),
None => true,
}
}
/// Whether the fragment's own leaf items can touch the damaged region.
pub(crate) fn own_intersects(&self, id: FragmentId, rects: &[Rect]) -> bool {
match self.records.get(&id) {
Some(record) => bounds_intersect(record.own, rects),
None => true,
}
}
}
/// One prepass over the fragment tree: refresh records, collect damage.
struct Prepass<'a> {
store: &'a FragmentStore,
glyphs: &'a mut GlyphCache,
records: &'a mut HashMap<FragmentId, Record>,
stamp: u64,
damage: Vec<Rect>,
dag: bool,
}
impl Prepass<'_> {
/// Visit one fragment occurrence; returns its subtree device bounds.
fn fragment(
&mut self,
id: FragmentId,
base: Affine,
clip: Option<Rect>,
depth: usize,
) -> Result<Option<Rect>, RenderError> {
if depth > MAX_DEPTH {
return Err(RenderError::ExcessiveDepth(id));
}
let fragment = self.store.get(id).ok_or(RenderError::MissingFragment(id))?;
let epoch = self.store.epoch(id).expect("fragment exists");
let mut unchanged = false;
let mut old_subtree = None;
let mut recorded_own = None;
if let Some(prior) = self.records.get_mut(&id) {
if prior.stamp == self.stamp {
// Second encounter this frame: the fragment graph is a DAG.
self.dag = true;
return Ok(prior.subtree);
}
unchanged = prior.epoch == epoch && prior.transform == base && prior.clip == clip;
old_subtree = prior.subtree;
recorded_own = prior.own;
if unchanged && prior.leaf {
// Nothing inside an unchanged leaf can differ.
prior.stamp = self.stamp;
return Ok(prior.subtree);
}
}
let mut transform = base;
let mut transform_stack: Vec<Affine> = Vec::new();
let mut clip_stack: Vec<Option<Rect>> = Vec::new();
let mut current_clip = clip;
let mut scopes = ScopeTracker::default();
let unbalanced = || RenderError::UnbalancedFragment(id);
let mut own: Option<Rect> = None;
let mut children: Option<Rect> = None;
let mut leaf = true;
for item in &fragment.items {
if !scopes.apply(item) {
return Err(unbalanced());
}
match item {
DisplayItem::Fill { shape, .. } => {
if !unchanged {
let bounds = transform.transform_rect_bbox(shape.bounding_box());
own = union_clipped(own, bounds, current_clip);
}
}
DisplayItem::Stroke { shape, style, .. } => {
if !unchanged {
// Conservative: strokes extend past the shape by the
// cap radius or the miter extension, in local units.
let reach =
style.width * style.miter_limit.max(2.0) * transform_norm(transform);
let bounds = transform
.transform_rect_bbox(shape.bounding_box())
.inflate(reach, reach);
own = union_clipped(own, bounds, current_clip);
}
}
DisplayItem::GlyphRun(run) => {
if !unchanged
&& let Some(bounds) =
crate::glyph::run_device_bounds(run, transform, self.glyphs)?
{
own = union_clipped(own, bounds, current_clip);
}
}
DisplayItem::Image { dest, .. } => {
if !unchanged {
let bounds = transform.transform_rect_bbox(*dest);
own = union_clipped(own, bounds, current_clip);
}
}
DisplayItem::PushClip(shape) => {
clip_stack.push(current_clip);
let bounds = transform.transform_rect_bbox(shape.bounding_box());
current_clip = Some(match current_clip {
Some(clip) => intersect(clip, bounds).unwrap_or(Rect::ZERO),
None => bounds,
});
}
DisplayItem::PushLayer { bounds, .. } => {
// Layer contents composite masked to the layer bounds, so
// for damage geometry a layer clips like a clip.
clip_stack.push(current_clip);
let bounds = transform.transform_rect_bbox(bounds.bounding_box());
current_clip = Some(match current_clip {
Some(clip) => intersect(clip, bounds).unwrap_or(Rect::ZERO),
None => bounds,
});
}
DisplayItem::PopClip | DisplayItem::PopLayer => {
current_clip = clip_stack.pop().ok_or_else(unbalanced)?;
}
DisplayItem::PushTransform(t) => {
transform_stack.push(transform);
transform *= *t;
}
DisplayItem::PopTransform => {
transform = transform_stack.pop().ok_or_else(unbalanced)?;
}
DisplayItem::Child {
transform: placement,
fragment,
} => {
leaf = false;
let subtree =
self.fragment(*fragment, transform * *placement, current_clip, depth + 1)?;
children = union_bounds(children, subtree);
}
}
}
if !scopes.is_closed() || !transform_stack.is_empty() {
return Err(unbalanced());
}
let own = if unchanged { recorded_own } else { own };
let subtree = union_bounds(own, children);
if !unchanged {
if let Some(bounds) = old_subtree {
self.damage.push(bounds);
}
if let Some(bounds) = subtree {
self.damage.push(bounds);
}
}
self.records.insert(
id,
Record {
epoch,
transform: base,
clip,
own,
subtree,
leaf,
stamp: self.stamp,
},
);
Ok(subtree)
}
}
/// Union `bounds ∩ clip` into `acc`.
fn union_clipped(acc: Option<Rect>, bounds: Rect, clip: Option<Rect>) -> Option<Rect> {
let clipped = match clip {
Some(clip) => match intersect(bounds, clip) {
Some(rect) => rect,
None => return acc,
},
None => bounds,
};
union_bounds(acc, Some(clipped))
}
fn union_bounds(a: Option<Rect>, b: Option<Rect>) -> Option<Rect> {
match (a, b) {
(Some(a), Some(b)) => Some(a.union(b)),
(Some(a), None) => Some(a),
(None, b) => b,
}
}
/// Rect intersection, `None` when empty.
fn intersect(a: Rect, b: Rect) -> Option<Rect> {
let rect = a.intersect(b);
(rect.width() > 0.0 && rect.height() > 0.0).then_some(rect)
}
fn contains(outer: Rect, inner: Rect) -> bool {
outer.x0 <= inner.x0 && outer.y0 <= inner.y0 && outer.x1 >= inner.x1 && outer.y1 >= inner.y1
}
/// Pad a pixel for anti-aliasing and round outward to the pixel grid.
fn pad_round(rect: Rect) -> Rect {
Rect::new(
(rect.x0 - 1.0).floor(),
(rect.y0 - 1.0).floor(),
(rect.x1 + 1.0).ceil(),
(rect.y1 + 1.0).ceil(),
)
}
/// An upper bound on how much the transform can scale any direction (the
/// Frobenius norm bounds the largest singular value).
fn transform_norm(t: Affine) -> f64 {
let [xx, yx, xy, yy, ..] = t.as_coeffs();
(xx * xx + yx * yx + xy * xy + yy * yy).sqrt()
}
/// Whether recorded bounds (inflated a pixel for AA) touch any damage rect.
fn bounds_intersect(bounds: Option<Rect>, rects: &[Rect]) -> bool {
let Some(bounds) = bounds else {
return false;
};
let bounds = bounds.inflate(1.0, 1.0);
rects.iter().any(|rect| intersect(bounds, *rect).is_some())
}
#[cfg(test)]
mod tests {
use guiduck_scene::Fragment;
use guiduck_scene::paint::color::palette::css;
use super::*;
fn fill_fragment(rect: Rect) -> Fragment {
let mut fragment = Fragment::new();
fragment.fill(rect, css::REBECCA_PURPLE);
fragment
}
fn plan(
tracker: &mut DamageTracker,
root: FragmentId,
store: &FragmentStore,
glyphs: &mut GlyphCache,
) -> Damage {
tracker
.plan(root, store, 200, 100, 1.0, Color::WHITE, glyphs)
.expect("plan succeeds")
}
#[test]
fn unchanged_store_needs_no_repaint() {
let mut store = FragmentStore::new();
let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut root = Fragment::new();
root.fill(Rect::new(0.0, 0.0, 200.0, 100.0), css::WHITE);
root.child(Affine::translate((20.0, 20.0)), child);
let root = store.insert(root);
let mut tracker = DamageTracker::default();
let mut glyphs = GlyphCache::default();
assert!(matches!(
plan(&mut tracker, root, &store, &mut glyphs),
Damage::Full
));
let Damage::Partial(rects) = plan(&mut tracker, root, &store, &mut glyphs) else {
panic!("unchanged frame should be partial");
};
assert!(rects.is_empty(), "no damage expected, got {rects:?}");
}
#[test]
fn moved_content_damages_old_and_new_bounds() {
let mut store = FragmentStore::new();
let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut root = Fragment::new();
root.child(Affine::translate((20.0, 20.0)), child);
let root_id = store.insert(root);
let mut tracker = DamageTracker::default();
let mut glyphs = GlyphCache::default();
plan(&mut tracker, root_id, &store, &mut glyphs);
// Move the child to the other side of the viewport.
let fragment = store.get_mut(root_id).expect("root exists");
fragment.clear();
fragment.child(Affine::translate((150.0, 60.0)), child);
let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
panic!("expected partial damage");
};
let covers = |x: f64, y: f64| {
rects
.iter()
.any(|r| r.contains(guiduck_scene::geom::Point::new(x, y)))
};
assert!(covers(25.0, 25.0), "old position damaged: {rects:?}");
assert!(covers(155.0, 65.0), "new position damaged: {rects:?}");
assert!(
!covers(100.0, 50.0),
"untouched middle undamaged: {rects:?}"
);
}
#[test]
fn removed_content_damages_its_parent_but_not_unrelated_subtrees() {
// root → left(child), right(keeper): removing `child` rewrites
// `left`, so `left`'s region is damage — `right`'s is not.
let mut store = FragmentStore::new();
let child = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let keeper = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut left = Fragment::new();
left.child(Affine::translate((0.0, 0.0)), child);
let left = store.insert(left);
let mut right = Fragment::new();
right.child(Affine::translate((0.0, 0.0)), keeper);
let right = store.insert(right);
let mut root = Fragment::new();
root.child(Affine::translate((20.0, 20.0)), left);
root.child(Affine::translate((150.0, 60.0)), right);
let root_id = store.insert(root);
let mut tracker = DamageTracker::default();
let mut glyphs = GlyphCache::default();
plan(&mut tracker, root_id, &store, &mut glyphs);
let fragment = store.get_mut(left).expect("left exists");
fragment.clear();
store.remove(child);
let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
panic!("expected partial damage");
};
assert!(
rects
.iter()
.any(|r| r.contains(guiduck_scene::geom::Point::new(25.0, 25.0))),
"removed child's old position damaged: {rects:?}"
);
assert!(
!rects
.iter()
.any(|r| r.contains(guiduck_scene::geom::Point::new(155.0, 65.0))),
"unrelated subtree undamaged: {rects:?}"
);
}
#[test]
fn different_store_forces_full_repaint() {
let mut store_a = FragmentStore::new();
let root_a = store_a.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut store_b = FragmentStore::new();
let root_b = store_b.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut tracker = DamageTracker::default();
let mut glyphs = GlyphCache::default();
plan(&mut tracker, root_a, &store_a, &mut glyphs);
assert!(matches!(
plan(&mut tracker, root_b, &store_b, &mut glyphs),
Damage::Full
));
assert!(matches!(
plan(&mut tracker, root_a, &store_a, &mut glyphs),
Damage::Full
));
}
#[test]
fn dag_input_forces_full_repaint() {
let mut store = FragmentStore::new();
let shared = store.insert(fill_fragment(Rect::new(0.0, 0.0, 10.0, 10.0)));
let mut root = Fragment::new();
root.child(Affine::translate((20.0, 20.0)), shared);
root.child(Affine::translate((60.0, 20.0)), shared);
let root_id = store.insert(root);
let mut tracker = DamageTracker::default();
let mut glyphs = GlyphCache::default();
assert!(matches!(
plan(&mut tracker, root_id, &store, &mut glyphs),
Damage::Full
));
// An untouched store needs no repaint even after a DAG frame — the
// pixmap already holds a correct full render.
let Damage::Partial(rects) = plan(&mut tracker, root_id, &store, &mut glyphs) else {
panic!("unchanged store should skip repainting");
};
assert!(rects.is_empty());
// But any mutation goes back to full: one record per id cannot
// describe two occurrences, so the tracker never trusts a DAG.
store
.get_mut(shared)
.expect("shared exists")
.fill(Rect::new(0.0, 0.0, 5.0, 5.0), css::WHITE);
assert!(matches!(
plan(&mut tracker, root_id, &store, &mut glyphs),
Damage::Full
));
}
}