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. Keep one per window.
137#[derive(Debug)]
138pub struct DamageHistory {
139  id: u64,
140  /// The number the next frame gets.
141  next: u64,
142  /// The buffer size and scale of the last frame. Another size or scale
143  /// changes every pixel.
144  shape: Option<(u32, u32, u32)>,
145  /// The damage of recent frames, oldest first.
146  recent: VecDeque<(u64, Vec<PixelRect>)>,
147}
148
149/// What one frame repaints and reports.
150#[derive(Debug, PartialEq, Eq)]
151pub(crate) struct Plan {
152  /// The areas to repaint, none overlapping: this frame's damage and
153  /// whatever changed in frames the buffer missed.
154  pub(crate) repaint: Vec<PixelRect>,
155  /// The areas that differ from the last frame the compositor showed, for
156  /// `wl_surface.damage_buffer`.
157  pub(crate) report: Vec<PixelRect>,
158}
159
160impl Default for DamageHistory {
161  fn default() -> Self {
162    Self::new()
163  }
164}
165
166impl DamageHistory {
167  /// Names the history, and so its window, for the caches.
168  pub(crate) fn id(&self) -> u64 {
169    self.id
170  }
171
172  /// A history with no frames yet; the first frame repaints everything.
173  pub fn new() -> DamageHistory {
174    DamageHistory {
175      id: HISTORIES.fetch_add(1, Ordering::Relaxed),
176      next: 0,
177      shape: None,
178      recent: VecDeque::new(),
179    }
180  }
181
182  /// Works out what a frame with logical `damage` repaints in a `width` by
183  /// `height` buffer at `scale` that last held the frame in `age`, and
184  /// records the frame as the buffer's.
185  pub(crate) fn plan(
186    &mut self,
187    damage: &[Rect],
188    scale: f32,
189    width: u32,
190    height: u32,
191    age: &mut BufferAge,
192  ) -> Plan {
193    let full = vec![PixelRect::new(0, 0, width, height)];
194    let frame = self.next;
195    self.next += 1;
196
197    let shape = (width, height, scale.to_bits());
198    let mut changed = if self.shape == Some(shape) {
199      merge(
200        damage
201          .iter()
202          .filter_map(|rect| to_pixels(*rect, scale, width, height))
203          .collect(),
204      )
205    } else {
206      // A new size or scale changes every pixel, and earlier frames say
207      // nothing about this one.
208      self.shape = Some(shape);
209      self.recent.clear();
210      full.clone()
211    };
212    if more_than_half(&changed, width, height) {
213      changed = full.clone();
214    }
215
216    // Frames the buffer missed, if it was this history's and the history
217    // still has them all.
218    let missed = match age.drawn {
219      Some((history, drawn))
220        if history == self.id
221          && self
222            .recent
223            .front()
224            .is_none_or(|(first, _)| *first <= drawn + 1) =>
225      {
226        Some(
227          self
228            .recent
229            .iter()
230            .filter(|(number, _)| *number > drawn)
231            .flat_map(|(_, rects)| rects.iter().copied())
232            .collect::<Vec<_>>(),
233        )
234      }
235      _ => None,
236    };
237    let repaint = match missed {
238      Some(missed) => {
239        let repaint = merge(changed.iter().copied().chain(missed).collect());
240        if more_than_half(&repaint, width, height) {
241          full
242        } else {
243          repaint
244        }
245      }
246      None => full,
247    };
248
249    self.recent.push_back((frame, changed.clone()));
250    while self.recent.len() > HISTORY {
251      self.recent.pop_front();
252    }
253    age.drawn = Some((self.id, frame));
254    Plan {
255      repaint,
256      report: changed,
257    }
258  }
259}
260
261/// Whether non-overlapping `rects` cover more than half of the buffer, in
262/// which case repainting all of it is simpler and about as fast.
263fn more_than_half(rects: &[PixelRect], width: u32, height: u32) -> bool {
264  let covered: u64 = rects.iter().map(PixelRect::area).sum();
265  covered * 2 > u64::from(width) * u64::from(height)
266}