layout/display_list/
painted_region.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use euclid::{Box2D, Point2D};
6use webrender_api::units::LayoutPixel;
7
8/// A set of disjoint, axis-aligned rectangles that tracks exactly which area has
9/// already been painted for a Container Timing container, so that overlapping
10/// fragments (e.g. two overlapping `<img>`s) aren't double-counted.
11///
12/// Mirrors the approach Chromium's Container Timing implementation takes with
13/// `cc::Region`
14#[derive(Clone, Debug, Default)]
15pub(crate) struct PaintedRegion {
16    /// No two rects in this list overlap.
17    rects: Vec<Box2D<f32, LayoutPixel>>,
18}
19
20impl PaintedRegion {
21    /// The total painted area, i.e. the sum of the (disjoint) rects' areas.
22    pub(crate) fn area(&self) -> f32 {
23        self.rects.iter().map(Box2D::area).sum()
24    }
25
26    /// The smallest box containing every rect in this region.
27    pub(crate) fn bounds(&self) -> Box2D<f32, LayoutPixel> {
28        // Seeded from the first rect rather than `Box2D::zero()`: union-ing with the
29        // zero box would drag the bounds back to the origin for any region that does
30        // not already reach it.
31        self.rects
32            .iter()
33            .copied()
34            .reduce(|bounds, rect| bounds.union(&rect))
35            .unwrap_or_else(Box2D::zero)
36    }
37
38    /// Returns `true` if `rect` is already entirely covered by this region, i.e.
39    /// merging it in would add no new area.
40    pub(crate) fn contains(&self, rect: Box2D<f32, LayoutPixel>) -> bool {
41        if rect.is_empty() {
42            return true;
43        }
44        // Fast path: a single existing rect fully containing the new one is the
45        // common case (the same fragment, unchanged, revisited on
46        // an unrelated repaint).
47        if self
48            .rects
49            .iter()
50            .any(|existing| existing.contains_box(&rect))
51        {
52            return true;
53        }
54        subtract_all(rect, &self.rects).is_empty()
55    }
56
57    /// Merges `rect` into the region, splitting it against existing rects so the
58    /// region remains disjoint. (matches Chromium's use of
59    /// `gfx::ToEnclosingRect` before touching `cc::Region`).
60    pub(crate) fn union(&mut self, rect: Box2D<f32, LayoutPixel>) {
61        let rect = rect.round_out();
62        if rect.is_empty() || self.contains(rect) {
63            return;
64        }
65        self.rects.extend(subtract_all(rect, &self.rects));
66    }
67
68    pub(crate) fn merge(&mut self, other: &PaintedRegion) {
69        for &rect in &other.rects {
70            self.union(rect);
71        }
72    }
73}
74
75/// Returns the portion of `rect` not covered by any rect in `others`, as a set of
76/// disjoint rects (possibly empty, if `others` fully covers `rect`).
77fn subtract_all(
78    rect: Box2D<f32, LayoutPixel>,
79    others: &[Box2D<f32, LayoutPixel>],
80) -> Vec<Box2D<f32, LayoutPixel>> {
81    let mut pieces = vec![rect];
82    for other in others {
83        if pieces.is_empty() {
84            break;
85        }
86        pieces = pieces
87            .into_iter()
88            .flat_map(|piece| subtract_one(piece, *other))
89            .collect();
90    }
91    pieces
92}
93
94/// Splits `a` into the (up to four) disjoint rects that remain once `b` is removed
95/// from it.
96fn subtract_one(
97    a: Box2D<f32, LayoutPixel>,
98    b: Box2D<f32, LayoutPixel>,
99) -> Vec<Box2D<f32, LayoutPixel>> {
100    let Some(i) = a.intersection(&b) else {
101        return vec![a];
102    };
103    if i.is_empty() {
104        return vec![a];
105    }
106
107    let mut out = Vec::with_capacity(4);
108    if i.min.y > a.min.y {
109        out.push(Box2D::new(
110            Point2D::new(a.min.x, a.min.y),
111            Point2D::new(a.max.x, i.min.y),
112        ));
113    }
114    if i.max.y < a.max.y {
115        out.push(Box2D::new(
116            Point2D::new(a.min.x, i.max.y),
117            Point2D::new(a.max.x, a.max.y),
118        ));
119    }
120    if i.min.x > a.min.x {
121        out.push(Box2D::new(
122            Point2D::new(a.min.x, i.min.y),
123            Point2D::new(i.min.x, i.max.y),
124        ));
125    }
126    if i.max.x < a.max.x {
127        out.push(Box2D::new(
128            Point2D::new(i.max.x, i.min.y),
129            Point2D::new(a.max.x, i.max.y),
130        ));
131    }
132    out
133}
134
135#[cfg(test)]
136mod tests {
137    use euclid::Box2D;
138
139    use super::PaintedRegion;
140
141    fn rect(x0: f32, y0: f32, x1: f32, y1: f32) -> Box2D<f32, webrender_api::units::LayoutPixel> {
142        Box2D::new((x0, y0).into(), (x1, y1).into())
143    }
144
145    #[test]
146    fn repeated_identical_rect_does_not_grow() {
147        let mut region = PaintedRegion::default();
148        region.union(rect(0.0, 0.0, 10.0, 10.0));
149        assert_eq!(region.area(), 100.0);
150        for _ in 0..5 {
151            assert!(region.contains(rect(0.0, 0.0, 10.0, 10.0)));
152            region.union(rect(0.0, 0.0, 10.0, 10.0));
153        }
154        assert_eq!(region.area(), 100.0);
155    }
156
157    #[test]
158    fn overlapping_rects_are_not_double_counted() {
159        let mut region = PaintedRegion::default();
160        region.union(rect(0.0, 0.0, 10.0, 10.0));
161        region.union(rect(5.0, 5.0, 15.0, 15.0));
162        // Union of two 10x10 squares overlapping in a 5x5 corner: 100 + 100 - 25.
163        assert_eq!(region.area(), 175.0);
164        assert_eq!(region.bounds(), rect(0.0, 0.0, 15.0, 15.0));
165    }
166
167    #[test]
168    fn bounds_do_not_reach_back_to_the_origin() {
169        let mut region = PaintedRegion::default();
170        region.union(rect(100.0, 100.0, 200.0, 200.0));
171        assert_eq!(region.bounds(), rect(100.0, 100.0, 200.0, 200.0));
172    }
173
174    #[test]
175    fn disjoint_rects_sum() {
176        let mut region = PaintedRegion::default();
177        region.union(rect(0.0, 0.0, 10.0, 10.0));
178        region.union(rect(20.0, 20.0, 30.0, 30.0));
179        assert_eq!(region.area(), 200.0);
180    }
181
182    #[test]
183    fn fully_contained_rect_is_a_noop() {
184        let mut region = PaintedRegion::default();
185        region.union(rect(0.0, 0.0, 100.0, 100.0));
186        assert!(region.contains(rect(10.0, 10.0, 20.0, 20.0)));
187        region.union(rect(10.0, 10.0, 20.0, 20.0));
188        assert_eq!(region.area(), 10_000.0);
189    }
190
191    #[test]
192    fn empty_rect_is_a_noop() {
193        let mut region = PaintedRegion::default();
194        region.union(rect(5.0, 5.0, 5.0, 5.0));
195        assert_eq!(region.area(), 0.0);
196        assert!(region.contains(rect(5.0, 5.0, 5.0, 5.0)));
197    }
198}
layout/display_list/painted_region.rs

layout/display_list/
painted_region.rs
