Skip to main content

crabshell_render/
damage.rs

1//! Damage tracking: which pixels of a buffer to repaint, and which to report
2//! to the compositor.
3//!
4//! A window's damage arrives in logical pixels. It is turned into physical
5//! pixels, rounding outward, and overlapping rectangles are merged so that
6//! no pixel is repainted twice. Each buffer remembers the frame it last
7//! held, and a window's [`DamageHistory`] remembers what changed in recent
8//! frames, so a buffer that skipped frames also gets those areas repainted.
9
10use std::collections::VecDeque;
11use std::sync::atomic::{AtomicU64, Ordering};
12
13use crabshell_ui::Rect;
14
15/// How many frames of damage a history keeps. A window has two or three
16/// buffers, so a buffer reused at all is at most this many frames behind.
17const HISTORY: usize = 4;
18
19/// Physical pixels added around every damaged rectangle, for antialiased
20/// edges and glyphs that reach a pixel past the area layout gave them.
21const MARGIN: u32 = 1;
22
23/// A rectangle of buffer pixels.
24#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
25pub struct PixelRect {
26  /// The left edge.
27  pub x: u32,
28  /// The top edge.
29  pub y: u32,
30  /// The width.
31  pub width: u32,
32  /// The height.
33  pub height: u32,
34}
35
36impl PixelRect {
37  /// A rectangle with its top-left corner at `x`, `y`.
38  pub const fn new(x: u32, y: u32, width: u32, height: u32) -> PixelRect {
39    PixelRect {
40      x,
41      y,
42      width,
43      height,
44    }
45  }
46
47  /// The right edge, one past the last column.
48  pub fn right(&self) -> u32 {
49    self.x + self.width
50  }
51
52  /// The bottom edge, one past the last row.
53  pub fn bottom(&self) -> u32 {
54    self.y + self.height
55  }
56
57  /// The number of pixels.
58  pub fn area(&self) -> u64 {
59    u64::from(self.width) * u64::from(self.height)
60  }
61
62  /// Whether the two share any pixel.
63  pub fn overlaps(&self, other: &PixelRect) -> bool {
64    self.x < other.right()
65      && other.x < self.right()
66      && self.y < other.bottom()
67      && other.y < self.bottom()
68  }
69
70  /// The smallest rectangle covering both.
71  fn union(&self, other: &PixelRect) -> PixelRect {
72    let x = self.x.min(other.x);
73    let y = self.y.min(other.y);
74    PixelRect::new(
75      x,
76      y,
77      self.right().max(other.right()) - x,
78      self.bottom().max(other.bottom()) - y,
79    )
80  }
81}
82
83/// Converts a logical rectangle to the buffer pixels it touches at `scale`,
84/// rounding outward and adding [`MARGIN`], clipped to a `width` by `height`
85/// buffer. `None` if nothing is left.
86pub(crate) fn to_pixels(rect: Rect, scale: f32, width: u32, height: u32) -> Option<PixelRect> {
87  if !(rect.width > 0.0 && rect.height > 0.0) {
88    return None;
89  }
90  // `as` saturates: negative values become 0, huge ones the maximum.
91  let left = ((rect.x * scale).floor() as u32).saturating_sub(MARGIN);
92  let top = ((rect.y * scale).floor() as u32).saturating_sub(MARGIN);
93  let right = ((rect.right() * scale).ceil() as u32)
94    .saturating_add(MARGIN)
95    .min(width);
96  let bottom = ((rect.bottom() * scale).ceil() as u32)
97    .saturating_add(MARGIN)
98    .min(height);
99  (left < right && top < bottom).then(|| PixelRect::new(left, top, right - left, bottom - top))
100}
101
102/// Merges overlapping rectangles into their bounding boxes until no two
103/// overlap, so every pixel is in at most one. Rectangles that only touch
104/// stay apart.
105pub(crate) fn merge(mut rects: Vec<PixelRect>) -> Vec<PixelRect> {
106  rects.retain(|rect| rect.area() > 0);
107  let mut merged = true;
108  while merged {
109    merged = false;
110    'outer: for i in 0..rects.len() {
111      for j in i + 1..rects.len() {
112        if rects[i].overlaps(&rects[j]) {
113          let other = rects.swap_remove(j);
114          rects[i] = rects[i].union(&other);
115          merged = true;
116          break 'outer;
117        }
118      }
119    }
120  }
121  rects
122}
123
124/// The frame a buffer last held. Keep one next to each buffer, starting
125/// with [`BufferAge::default`] for a new one.
126#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
127pub struct BufferAge {
128  /// The history and the number of the frame last drawn into the buffer.
129  drawn: Option<(u64, u64)>,
130}
131
132/// Gives every history its own id, so a buffer's age is only trusted by
133/// the history that drew it.
134static HISTORIES: AtomicU64 = AtomicU64::new(0);
135
136/// What changed in one window's recent frames, and the layers the
137/// renderer keeps while something in it fades or moves. Keep one per
138/// window; dropping it frees them.
139#[derive(Debug)]
140pub struct DamageHistory {
141  id: u64,
142  /// The number the next frame gets.
143  next: u64,
144  /// The buffer size and scale of the last frame. Another size or scale
145  /// changes every pixel.
146  shape: Option<(u32, u32, u32)>,
147  /// The damage of recent frames, oldest first.
148  recent: VecDeque<(u64, Vec<PixelRect>)>,
149  /// The layers the renderer keeps for the window's next draw.
150  pub(crate) kept: crate::draw::Kept,
151}
152
153/// What one frame repaints and reports.
154#[derive(Debug, PartialEq, Eq)]
155pub(crate) struct Plan {
156  /// The areas to repaint, none overlapping: this frame's damage and
157  /// whatever changed in frames the buffer missed.
158  pub(crate) repaint: Vec<PixelRect>,
159  /// The areas that differ from the last frame the compositor showed, for
160  /// `wl_surface.damage_buffer`.
161  pub(crate) report: Vec<PixelRect>,
162}
163
164impl Default for DamageHistory {
165  fn default() -> Self {
166    Self::new()
167  }
168}
169
170impl DamageHistory {
171  /// Names the history, and so its window, for the caches.
172  pub(crate) fn id(&self) -> u64 {
173    self.id
174  }
175
176  /// A history with no frames yet; the first frame repaints everything.
177  pub fn new() -> DamageHistory {
178    DamageHistory {
179      id: HISTORIES.fetch_add(1, Ordering::Relaxed),
180      next: 0,
181      shape: None,
182      recent: VecDeque::new(),
183      kept: crate::draw::Kept::default(),
184    }
185  }
186
187  /// Works out what a frame with logical `damage` repaints in a `width` by
188  /// `height` buffer at `scale` that last held the frame in `age`, and
189  /// records the frame as the buffer's.
190  pub(crate) fn plan(
191    &mut self,
192    damage: &[Rect],
193    scale: f32,
194    width: u32,
195    height: u32,
196    age: &mut BufferAge,
197  ) -> Plan {
198    let full = vec![PixelRect::new(0, 0, width, height)];
199    let frame = self.next;
200    self.next += 1;
201
202    let shape = (width, height, scale.to_bits());
203    let mut changed = if self.shape == Some(shape) {
204      merge(
205        damage
206          .iter()
207          .filter_map(|rect| to_pixels(*rect, scale, width, height))
208          .collect(),
209      )
210    } else {
211      // A new size or scale changes every pixel, and earlier frames say
212      // nothing about this one.
213      self.shape = Some(shape);
214      self.recent.clear();
215      full.clone()
216    };
217    if more_than_half(&changed, width, height) {
218      changed = full.clone();
219    }
220
221    // Frames the buffer missed, if it was this history's and the history
222    // still has them all.
223    let missed = match age.drawn {
224      Some((history, drawn))
225        if history == self.id
226          && self
227            .recent
228            .front()
229            .is_none_or(|(first, _)| *first <= drawn + 1) =>
230      {
231        Some(
232          self
233            .recent
234            .iter()
235            .filter(|(number, _)| *number > drawn)
236            .flat_map(|(_, rects)| rects.iter().copied())
237            .collect::<Vec<_>>(),
238        )
239      }
240      _ => None,
241    };
242    let repaint = match missed {
243      Some(missed) => {
244        let repaint = merge(changed.iter().copied().chain(missed).collect());
245        if more_than_half(&repaint, width, height) {
246          full
247        } else {
248          repaint
249        }
250      }
251      None => full,
252    };
253
254    self.recent.push_back((frame, changed.clone()));
255    while self.recent.len() > HISTORY {
256      self.recent.pop_front();
257    }
258    age.drawn = Some((self.id, frame));
259    Plan {
260      repaint,
261      report: changed,
262    }
263  }
264}
265
266/// Whether non-overlapping `rects` cover more than half of the buffer, in
267/// which case repainting all of it is simpler and about as fast.
268fn more_than_half(rects: &[PixelRect], width: u32, height: u32) -> bool {
269  let covered: u64 = rects.iter().map(PixelRect::area).sum();
270  covered * 2 > u64::from(width) * u64::from(height)
271}