veridian_kernel/graphics/
damage_tracking.rs

1//! Damage Tracking for Compositor Re-composition
2//!
3//! Per-surface dirty-rect list with merge algorithm. The compositor
4//! re-composites only damaged regions instead of the full framebuffer,
5//! dramatically reducing fill-rate pressure on software renderers
6//! (llvmpipe / CPU blitter).
7//!
8//! All arithmetic uses integer math (no FPU required).
9
10#![allow(dead_code)]
11
12use alloc::vec::Vec;
13
14use spin::Mutex;
15
16// ---------------------------------------------------------------------------
17// Constants
18// ---------------------------------------------------------------------------
19
20/// Maximum number of damage rects per surface before we fall back to
21/// full-surface damage. Keeps merge cost bounded.
22const MAX_DAMAGE_RECTS: usize = 32;
23
24/// Maximum number of tracked surfaces.
25const MAX_SURFACES: usize = 256;
26
27// ---------------------------------------------------------------------------
28// DamageRect
29// ---------------------------------------------------------------------------
30
31/// Axis-aligned damage rectangle (integer coordinates).
32#[derive(Debug, Clone, Copy, PartialEq, Eq)]
33pub(crate) struct DamageRect {
34    pub x: i32,
35    pub y: i32,
36    pub width: u32,
37    pub height: u32,
38}
39
40impl DamageRect {
41    /// Create a new damage rect.
42    pub(crate) fn new(x: i32, y: i32, width: u32, height: u32) -> Self {
43        Self {
44            x,
45            y,
46            width,
47            height,
48        }
49    }
50
51    /// Right edge (exclusive).
52    #[inline]
53    pub(crate) fn right(&self) -> i32 {
54        self.x.saturating_add(self.width as i32)
55    }
56
57    /// Bottom edge (exclusive).
58    #[inline]
59    pub(crate) fn bottom(&self) -> i32 {
60        self.y.saturating_add(self.height as i32)
61    }
62
63    /// Area in pixels.
64    #[inline]
65    pub(crate) fn area(&self) -> u64 {
66        self.width as u64 * self.height as u64
67    }
68
69    /// True when this rect has zero area.
70    #[inline]
71    pub(crate) fn is_empty(&self) -> bool {
72        self.width == 0 || self.height == 0
73    }
74
75    /// Check if two rects overlap.
76    #[inline]
77    fn overlaps(&self, other: &DamageRect) -> bool {
78        self.x < other.right()
79            && other.x < self.right()
80            && self.y < other.bottom()
81            && other.y < self.bottom()
82    }
83
84    /// Check if two rects touch (overlap or share an edge).
85    #[inline]
86    fn touches(&self, other: &DamageRect) -> bool {
87        self.x <= other.right()
88            && other.x <= self.right()
89            && self.y <= other.bottom()
90            && other.y <= self.bottom()
91    }
92
93    /// Compute the bounding-box union of two rects.
94    fn union(&self, other: &DamageRect) -> DamageRect {
95        let x = self.x.min(other.x);
96        let y = self.y.min(other.y);
97        let r = self.right().max(other.right());
98        let b = self.bottom().max(other.bottom());
99        DamageRect {
100            x,
101            y,
102            width: (r - x) as u32,
103            height: (b - y) as u32,
104        }
105    }
106
107    /// Compute the intersection of two rects (may be empty).
108    fn intersect(&self, other: &DamageRect) -> DamageRect {
109        let x = self.x.max(other.x);
110        let y = self.y.max(other.y);
111        let r = self.right().min(other.right());
112        let b = self.bottom().min(other.bottom());
113        if r <= x || b <= y {
114            DamageRect::new(0, 0, 0, 0)
115        } else {
116            DamageRect::new(x, y, (r - x) as u32, (b - y) as u32)
117        }
118    }
119
120    /// Clamp this rect to fit within `bounds`.
121    pub(crate) fn clamp_to(&self, bounds: &DamageRect) -> DamageRect {
122        self.intersect(bounds)
123    }
124}
125
126// ---------------------------------------------------------------------------
127// Per-surface damage list
128// ---------------------------------------------------------------------------
129
130/// Damage state for one surface.
131#[derive(Debug, Clone)]
132struct SurfaceDamage {
133    surface_id: u64,
134    rects: Vec<DamageRect>,
135    /// Surface dimensions (for full-surface fallback).
136    surface_width: u32,
137    surface_height: u32,
138    /// Set when the rect count exceeds the threshold; means "entire surface".
139    full_damage: bool,
140}
141
142impl SurfaceDamage {
143    fn new(surface_id: u64, width: u32, height: u32) -> Self {
144        Self {
145            surface_id,
146            rects: Vec::new(),
147            surface_width: width,
148            surface_height: height,
149            full_damage: false,
150        }
151    }
152
153    fn clear(&mut self) {
154        self.rects.clear();
155        self.full_damage = false;
156    }
157
158    fn has_damage(&self) -> bool {
159        self.full_damage || !self.rects.is_empty()
160    }
161
162    /// Mark the entire surface damaged.
163    fn mark_full(&mut self) {
164        self.rects.clear();
165        self.rects.push(DamageRect::new(
166            0,
167            0,
168            self.surface_width,
169            self.surface_height,
170        ));
171        self.full_damage = true;
172    }
173
174    fn add(&mut self, rect: DamageRect) {
175        if self.full_damage {
176            return; // already full
177        }
178        if rect.is_empty() {
179            return;
180        }
181        self.rects.push(rect);
182        if self.rects.len() > MAX_DAMAGE_RECTS {
183            self.mark_full();
184        }
185    }
186}
187
188// ---------------------------------------------------------------------------
189// DamageTracker
190// ---------------------------------------------------------------------------
191
192/// Global damage tracker managing per-surface dirty regions.
193pub(crate) struct DamageTracker {
194    surfaces: Vec<SurfaceDamage>,
195    /// Accumulated compositor-level damage (union of all surface damage
196    /// projected into screen coordinates).
197    screen_damage: Vec<DamageRect>,
198}
199
200impl DamageTracker {
201    /// Create a new empty tracker.
202    pub(crate) fn new() -> Self {
203        Self {
204            surfaces: Vec::new(),
205            screen_damage: Vec::new(),
206        }
207    }
208
209    // -- Surface registration ------------------------------------------------
210
211    /// Register a surface for tracking. Must be called before `add_damage`.
212    pub(crate) fn register_surface(&mut self, surface_id: u64, width: u32, height: u32) {
213        if self.find(surface_id).is_none() && self.surfaces.len() < MAX_SURFACES {
214            self.surfaces
215                .push(SurfaceDamage::new(surface_id, width, height));
216        }
217    }
218
219    /// Unregister a surface.
220    pub(crate) fn unregister_surface(&mut self, surface_id: u64) {
221        self.surfaces.retain(|s| s.surface_id != surface_id);
222    }
223
224    /// Update surface dimensions (e.g. on resize).
225    pub(crate) fn resize_surface(&mut self, surface_id: u64, width: u32, height: u32) {
226        if let Some(s) = self.find_mut(surface_id) {
227            s.surface_width = width;
228            s.surface_height = height;
229            // Resize implies full redraw
230            s.mark_full();
231        }
232    }
233
234    // -- Damage submission ---------------------------------------------------
235
236    /// Add a damage rect for a specific surface.
237    pub(crate) fn add_damage(&mut self, surface_id: u64, rect: DamageRect) {
238        if let Some(s) = self.find_mut(surface_id) {
239            s.add(rect);
240        }
241    }
242
243    /// Mark an entire surface as damaged.
244    pub(crate) fn add_full_damage(&mut self, surface_id: u64) {
245        if let Some(s) = self.find_mut(surface_id) {
246            s.mark_full();
247        }
248    }
249
250    // -- Queries -------------------------------------------------------------
251
252    /// Get the current damage rects for a surface.
253    pub(crate) fn get_damage(&self, surface_id: u64) -> &[DamageRect] {
254        match self.find(surface_id) {
255            Some(s) => &s.rects,
256            None => &[],
257        }
258    }
259
260    /// Check whether a surface has any pending damage.
261    pub(crate) fn has_damage(&self, surface_id: u64) -> bool {
262        self.find(surface_id).is_some_and(|s| s.has_damage())
263    }
264
265    /// Check whether any surface has pending damage.
266    pub(crate) fn has_any_damage(&self) -> bool {
267        self.surfaces.iter().any(|s| s.has_damage())
268    }
269
270    // -- Merge algorithm -----------------------------------------------------
271
272    /// Merge a list of rects by combining overlapping/touching rects.
273    ///
274    /// Uses a greedy merge: iterate pairs, merge touching rects, repeat
275    /// until stable. Worst-case O(n^2) per pass but n <= MAX_DAMAGE_RECTS.
276    pub(crate) fn merge_damage(rects: &[DamageRect]) -> Vec<DamageRect> {
277        if rects.is_empty() {
278            return Vec::new();
279        }
280        let mut merged: Vec<DamageRect> = rects.to_vec();
281
282        loop {
283            let mut changed = false;
284            let mut i = 0;
285            while i < merged.len() {
286                let mut j = i + 1;
287                while j < merged.len() {
288                    if merged[i].touches(&merged[j]) {
289                        // Check that merging doesn't waste too much area.
290                        // If the union area is less than 2x the sum of
291                        // individual areas, merge them.
292                        let union = merged[i].union(&merged[j]);
293                        let sum_area = merged[i].area().saturating_add(merged[j].area());
294                        let union_area = union.area();
295                        if union_area <= sum_area.saturating_mul(2) {
296                            merged[i] = union;
297                            merged.swap_remove(j);
298                            changed = true;
299                            continue; // re-check j (new element swapped in)
300                        }
301                    }
302                    j += 1;
303                }
304                i += 1;
305            }
306            if !changed {
307                break;
308            }
309        }
310
311        merged
312    }
313
314    /// Get merged damage for a surface.
315    pub(crate) fn get_merged_damage(&self, surface_id: u64) -> Vec<DamageRect> {
316        let rects = self.get_damage(surface_id);
317        Self::merge_damage(rects)
318    }
319
320    /// Compute screen-space damage from all surfaces.
321    ///
322    /// Each surface's damage rects are offset by `(sx, sy)` (the surface
323    /// position on screen), then merged into a single list.
324    pub(crate) fn compute_screen_damage(
325        &mut self,
326        surface_positions: &[(u64, i32, i32)], // (surface_id, x, y)
327    ) -> Vec<DamageRect> {
328        let mut all_rects: Vec<DamageRect> = Vec::new();
329
330        for &(sid, sx, sy) in surface_positions {
331            if let Some(s) = self.find(sid) {
332                for r in &s.rects {
333                    all_rects.push(DamageRect::new(
334                        r.x.saturating_add(sx),
335                        r.y.saturating_add(sy),
336                        r.width,
337                        r.height,
338                    ));
339                }
340            }
341        }
342
343        Self::merge_damage(&all_rects)
344    }
345
346    // -- Clear ---------------------------------------------------------------
347
348    /// Clear damage for a specific surface (after compositing).
349    pub(crate) fn clear_damage(&mut self, surface_id: u64) {
350        if let Some(s) = self.find_mut(surface_id) {
351            s.clear();
352        }
353    }
354
355    /// Clear all surface damage (after a full composite pass).
356    pub(crate) fn clear_all(&mut self) {
357        for s in &mut self.surfaces {
358            s.clear();
359        }
360        self.screen_damage.clear();
361    }
362
363    // -- Internals -----------------------------------------------------------
364
365    fn find(&self, surface_id: u64) -> Option<&SurfaceDamage> {
366        self.surfaces.iter().find(|s| s.surface_id == surface_id)
367    }
368
369    fn find_mut(&mut self, surface_id: u64) -> Option<&mut SurfaceDamage> {
370        self.surfaces
371            .iter_mut()
372            .find(|s| s.surface_id == surface_id)
373    }
374}
375
376// ---------------------------------------------------------------------------
377// Global instance
378// ---------------------------------------------------------------------------
379
380static DAMAGE_TRACKER: Mutex<Option<DamageTracker>> = Mutex::new(None);
381
382/// Initialize the global damage tracker.
383pub(crate) fn init() {
384    let mut guard = DAMAGE_TRACKER.lock();
385    if guard.is_none() {
386        *guard = Some(DamageTracker::new());
387    }
388}
389
390/// Access the global damage tracker.
391pub(crate) fn with_tracker<R, F: FnOnce(&mut DamageTracker) -> R>(f: F) -> Option<R> {
392    DAMAGE_TRACKER.lock().as_mut().map(f)
393}
394
395// ===========================================================================
396// Tests
397// ===========================================================================
398
399#[cfg(test)]
400mod tests {
401    use super::*;
402
403    #[test]
404    fn test_damage_rect_new() {
405        let r = DamageRect::new(10, 20, 100, 200);
406        assert_eq!(r.x, 10);
407        assert_eq!(r.y, 20);
408        assert_eq!(r.width, 100);
409        assert_eq!(r.height, 200);
410    }
411
412    #[test]
413    fn test_damage_rect_edges() {
414        let r = DamageRect::new(10, 20, 100, 50);
415        assert_eq!(r.right(), 110);
416        assert_eq!(r.bottom(), 70);
417    }
418
419    #[test]
420    fn test_damage_rect_area() {
421        let r = DamageRect::new(0, 0, 100, 200);
422        assert_eq!(r.area(), 20_000);
423    }
424
425    #[test]
426    fn test_damage_rect_empty() {
427        assert!(DamageRect::new(0, 0, 0, 100).is_empty());
428        assert!(DamageRect::new(0, 0, 100, 0).is_empty());
429        assert!(!DamageRect::new(0, 0, 1, 1).is_empty());
430    }
431
432    #[test]
433    fn test_damage_rect_overlap() {
434        let a = DamageRect::new(0, 0, 100, 100);
435        let b = DamageRect::new(50, 50, 100, 100);
436        assert!(a.overlaps(&b));
437        assert!(b.overlaps(&a));
438
439        let c = DamageRect::new(200, 200, 10, 10);
440        assert!(!a.overlaps(&c));
441    }
442
443    #[test]
444    fn test_damage_rect_touches() {
445        // Adjacent (sharing edge)
446        let a = DamageRect::new(0, 0, 100, 100);
447        let b = DamageRect::new(100, 0, 100, 100);
448        assert!(a.touches(&b));
449        assert!(!a.overlaps(&b)); // edge-sharing is not overlap
450
451        // Gap between them
452        let c = DamageRect::new(101, 0, 100, 100);
453        assert!(!a.touches(&c));
454    }
455
456    #[test]
457    fn test_damage_rect_union() {
458        let a = DamageRect::new(10, 20, 100, 50);
459        let b = DamageRect::new(50, 30, 200, 80);
460        let u = a.union(&b);
461        assert_eq!(u.x, 10);
462        assert_eq!(u.y, 20);
463        assert_eq!(u.right(), 250);
464        assert_eq!(u.bottom(), 110);
465        assert_eq!(u.width, 240);
466        assert_eq!(u.height, 90);
467    }
468
469    #[test]
470    fn test_damage_rect_intersect() {
471        let a = DamageRect::new(0, 0, 100, 100);
472        let b = DamageRect::new(50, 50, 100, 100);
473        let i = a.intersect(&b);
474        assert_eq!(i.x, 50);
475        assert_eq!(i.y, 50);
476        assert_eq!(i.width, 50);
477        assert_eq!(i.height, 50);
478
479        // Non-overlapping -> empty
480        let c = DamageRect::new(200, 200, 10, 10);
481        let empty = a.intersect(&c);
482        assert!(empty.is_empty());
483    }
484
485    #[test]
486    fn test_damage_rect_clamp() {
487        let r = DamageRect::new(-10, -10, 50, 50);
488        let bounds = DamageRect::new(0, 0, 1920, 1080);
489        let clamped = r.clamp_to(&bounds);
490        assert_eq!(clamped.x, 0);
491        assert_eq!(clamped.y, 0);
492        assert_eq!(clamped.width, 40);
493        assert_eq!(clamped.height, 40);
494    }
495
496    #[test]
497    fn test_tracker_register_and_damage() {
498        let mut tracker = DamageTracker::new();
499        tracker.register_surface(1, 800, 600);
500        assert!(!tracker.has_damage(1));
501
502        tracker.add_damage(1, DamageRect::new(0, 0, 100, 100));
503        assert!(tracker.has_damage(1));
504        assert_eq!(tracker.get_damage(1).len(), 1);
505    }
506
507    #[test]
508    fn test_tracker_clear_damage() {
509        let mut tracker = DamageTracker::new();
510        tracker.register_surface(1, 800, 600);
511        tracker.add_damage(1, DamageRect::new(0, 0, 50, 50));
512        tracker.clear_damage(1);
513        assert!(!tracker.has_damage(1));
514        assert_eq!(tracker.get_damage(1).len(), 0);
515    }
516
517    #[test]
518    fn test_tracker_full_damage_fallback() {
519        let mut tracker = DamageTracker::new();
520        tracker.register_surface(1, 800, 600);
521        // Exceed threshold
522        for i in 0..MAX_DAMAGE_RECTS + 5 {
523            tracker.add_damage(1, DamageRect::new(i as i32 * 10, 0, 5, 5));
524        }
525        // Should have collapsed to one full-surface rect
526        assert!(tracker.has_damage(1));
527        let rects = tracker.get_damage(1);
528        assert_eq!(rects.len(), 1);
529        assert_eq!(rects[0].width, 800);
530        assert_eq!(rects[0].height, 600);
531    }
532
533    #[test]
534    fn test_tracker_unregister() {
535        let mut tracker = DamageTracker::new();
536        tracker.register_surface(42, 640, 480);
537        tracker.add_damage(42, DamageRect::new(0, 0, 10, 10));
538        tracker.unregister_surface(42);
539        assert!(!tracker.has_damage(42));
540        assert_eq!(tracker.get_damage(42).len(), 0);
541    }
542
543    #[test]
544    fn test_tracker_resize_marks_full() {
545        let mut tracker = DamageTracker::new();
546        tracker.register_surface(1, 800, 600);
547        tracker.resize_surface(1, 1920, 1080);
548        assert!(tracker.has_damage(1));
549        let rects = tracker.get_damage(1);
550        assert_eq!(rects.len(), 1);
551        assert_eq!(rects[0].width, 1920);
552        assert_eq!(rects[0].height, 1080);
553    }
554
555    #[test]
556    fn test_merge_overlapping() {
557        let rects = vec![
558            DamageRect::new(0, 0, 100, 100),
559            DamageRect::new(50, 50, 100, 100),
560        ];
561        let merged = DamageTracker::merge_damage(&rects);
562        assert_eq!(merged.len(), 1);
563        assert_eq!(merged[0].x, 0);
564        assert_eq!(merged[0].y, 0);
565        assert_eq!(merged[0].width, 150);
566        assert_eq!(merged[0].height, 150);
567    }
568
569    #[test]
570    fn test_merge_non_overlapping() {
571        let rects = vec![
572            DamageRect::new(0, 0, 10, 10),
573            DamageRect::new(500, 500, 10, 10),
574        ];
575        let merged = DamageTracker::merge_damage(&rects);
576        // Far apart, should not merge (union area would be huge)
577        assert_eq!(merged.len(), 2);
578    }
579
580    #[test]
581    fn test_merge_empty() {
582        let merged = DamageTracker::merge_damage(&[]);
583        assert!(merged.is_empty());
584    }
585
586    #[test]
587    fn test_merge_adjacent() {
588        let rects = vec![
589            DamageRect::new(0, 0, 100, 100),
590            DamageRect::new(100, 0, 100, 100),
591        ];
592        let merged = DamageTracker::merge_damage(&rects);
593        assert_eq!(merged.len(), 1);
594        assert_eq!(merged[0].width, 200);
595    }
596
597    #[test]
598    fn test_has_any_damage() {
599        let mut tracker = DamageTracker::new();
600        tracker.register_surface(1, 100, 100);
601        tracker.register_surface(2, 100, 100);
602        assert!(!tracker.has_any_damage());
603
604        tracker.add_damage(2, DamageRect::new(0, 0, 10, 10));
605        assert!(tracker.has_any_damage());
606    }
607
608    #[test]
609    fn test_clear_all() {
610        let mut tracker = DamageTracker::new();
611        tracker.register_surface(1, 100, 100);
612        tracker.register_surface(2, 100, 100);
613        tracker.add_damage(1, DamageRect::new(0, 0, 10, 10));
614        tracker.add_damage(2, DamageRect::new(0, 0, 10, 10));
615        tracker.clear_all();
616        assert!(!tracker.has_any_damage());
617    }
618
619    #[test]
620    fn test_empty_rect_not_added() {
621        let mut tracker = DamageTracker::new();
622        tracker.register_surface(1, 800, 600);
623        tracker.add_damage(1, DamageRect::new(0, 0, 0, 0));
624        assert!(!tracker.has_damage(1));
625    }
626
627    #[test]
628    fn test_compute_screen_damage() {
629        let mut tracker = DamageTracker::new();
630        tracker.register_surface(1, 200, 200);
631        tracker.register_surface(2, 200, 200);
632
633        tracker.add_damage(1, DamageRect::new(0, 0, 50, 50));
634        tracker.add_damage(2, DamageRect::new(10, 10, 30, 30));
635
636        let positions = vec![(1, 100, 100), (2, 300, 300)];
637        let screen = tracker.compute_screen_damage(&positions);
638        // Two rects far apart, should not merge
639        assert_eq!(screen.len(), 2);
640    }
641
642    #[test]
643    fn test_damage_to_unregistered_surface() {
644        let mut tracker = DamageTracker::new();
645        // Should silently ignore
646        tracker.add_damage(999, DamageRect::new(0, 0, 10, 10));
647        assert!(!tracker.has_damage(999));
648    }
649}
veridian_kernel/graphics/damage_tracking.rs

veridian_kernel/graphics/
damage_tracking.rs
