webrender/
picture_graph.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 http://mozilla.org/MPL/2.0/. */
4
5use crate::frame_builder::FrameBuildingContext;
6use crate::internal_types::FastHashMap;
7use crate::prim_store::PictureIndex;
8use crate::picture::{PicturePrimitive, SurfaceIndex, SurfaceInfo};
9use crate::picture::{TileCacheInstance, SliceId};
10use smallvec::SmallVec;
11
12#[derive(Debug)]
13pub struct PictureInfo {
14    pub update_pass: Option<usize>,
15    pub surface_index: Option<SurfaceIndex>,
16    pub parent: Option<PictureIndex>,
17}
18
19#[derive(Default)]
20/// A graph of picture dependencies, allowing updates to be processed without recursion
21/// by building a list of passes.
22pub struct PictureGraph {
23    roots: Vec<PictureIndex>,
24    pic_info: Vec<PictureInfo>,
25    update_passes: Vec<Vec<PictureIndex>>,
26}
27
28impl PictureGraph {
29    pub fn new() -> Self {
30        PictureGraph::default()
31    }
32
33    pub fn reset(&mut self) {
34        self.roots.clear();
35        self.pic_info.clear();
36        self.update_passes.clear();
37    }
38
39    /// Add a root picture to the graph
40    pub fn add_root(
41        &mut self,
42        pic_index: PictureIndex,
43    ) {
44        self.roots.push(pic_index);
45    }
46
47    /// Build a list of update passes based on the dependencies between pictures
48    pub fn build_update_passes(
49        &mut self,
50        pictures: &mut [PicturePrimitive],
51        frame_context: &FrameBuildingContext
52    ) {
53        self.pic_info.clear();
54        self.pic_info.reserve(pictures.len());
55
56        for _ in 0 .. pictures.len() {
57            self.pic_info.push(PictureInfo {
58                update_pass: None,
59                parent: None,
60                surface_index: None,
61            })
62        };
63
64        let mut max_pass_index = 0;
65
66        for pic_index in &self.roots {
67            assign_update_pass(
68                *pic_index,
69                None,
70                0,
71                pictures,
72                &mut self.pic_info,
73                &mut max_pass_index,
74                frame_context,
75            );
76        }
77
78        let pass_count = max_pass_index + 1;
79
80        self.update_passes.clear();
81        self.update_passes.resize_with(pass_count, Vec::new);
82
83        for (pic_index, info) in self.pic_info.iter().enumerate() {
84            if let Some(update_pass) = info.update_pass {
85                let pass = &mut self.update_passes[update_pass];
86                pass.push(PictureIndex(pic_index));
87            }
88        }
89    }
90
91    /// Assign surfaces and scale factors to each picture (root -> leaf ordered pass)
92    pub fn assign_surfaces(
93        &mut self,
94        pictures: &mut [PicturePrimitive],
95        surfaces: &mut Vec<SurfaceInfo>,
96        tile_caches: &mut FastHashMap<SliceId, Box<TileCacheInstance>>,
97        frame_context: &FrameBuildingContext,
98    ) {
99        for pass in &self.update_passes {
100            for pic_index in pass {
101                let parent = self.pic_info[pic_index.0].parent;
102
103                let parent_surface_index = parent.map(|parent| {
104                    // Can unwrap here as by the time we have a parent that parent's
105                    // surface must have been assigned.
106                    self.pic_info[parent.0].surface_index.unwrap()
107                });
108
109                let info = &mut self.pic_info[pic_index.0];
110
111                match pictures[pic_index.0].assign_surface(
112                    frame_context,
113                    parent_surface_index,
114                    tile_caches,
115                    surfaces,
116                ) {
117                    Some(surface_index) => {
118                        info.surface_index = Some(surface_index);
119                    }
120                    None => {
121                        info.surface_index = Some(parent_surface_index.unwrap());
122                    }
123                }
124            }
125        }
126    }
127
128    /// Propegate bounding rects from pictures to parents (leaf -> root ordered pass)
129    pub fn propagate_bounding_rects(
130        &mut self,
131        pictures: &mut [PicturePrimitive],
132        surfaces: &mut [SurfaceInfo],
133        frame_context: &FrameBuildingContext,
134    ) {
135        for pass in self.update_passes.iter().rev() {
136            for pic_index in pass {
137                let parent = self.pic_info[pic_index.0].parent;
138
139                let surface_index = self.pic_info[pic_index.0]
140                    .surface_index
141                    .expect("bug: no surface assigned during propagate_bounding_rects");
142
143                let parent_surface_index = parent.map(|parent| {
144                    // Can unwrap here as by the time we have a parent that parent's
145                    // surface must have been assigned.
146                    self.pic_info[parent.0].surface_index.unwrap()
147                });
148
149                pictures[pic_index.0].propagate_bounding_rect(
150                    surface_index,
151                    parent_surface_index,
152                    surfaces,
153                    frame_context,
154                );
155            }
156        }
157    }
158}
159
160/// Recursive function that assigns pictures to the earliest pass possible that they
161/// can be processed in, while maintaining dependency ordering.
162fn assign_update_pass(
163    pic_index: PictureIndex,
164    parent_pic_index: Option<PictureIndex>,
165    pass: usize,
166    pictures: &mut [PicturePrimitive],
167    pic_info: &mut [PictureInfo],
168    max_pass_index: &mut usize,
169    frame_context: &FrameBuildingContext
170) {
171    let pic = &mut pictures[pic_index.0];
172    let info = &mut pic_info[pic_index.0];
173
174    info.parent = parent_pic_index;
175
176    // Run pre-update to resolve animation properties etc
177    pic.pre_update(frame_context);
178
179    let can_be_drawn = match info.update_pass {
180        Some(update_pass) => {
181            // No point in recursing into paths in the graph if this picture already
182            // has been set to update after this pass.
183            if update_pass > pass {
184                return;
185            }
186
187            true
188        }
189        None => {
190            // Check if this picture can be dropped from the graph we're building this frame
191            pic.is_visible(frame_context.spatial_tree)
192        }
193    };
194
195    if can_be_drawn {
196        info.update_pass = Some(pass);
197
198        *max_pass_index = pass.max(*max_pass_index);
199
200        let mut child_pictures: SmallVec<[PictureIndex; 8]> = SmallVec::new();
201        child_pictures.extend_from_slice(&pic.prim_list.child_pictures);
202
203        for child_pic_index in child_pictures {
204            assign_update_pass(
205                child_pic_index,
206                Some(pic_index),
207                pass + 1,
208                pictures,
209                pic_info,
210                max_pass_index,
211                frame_context,
212            );
213        }
214    }
215}