commit 448ac4309f904559eed37e781e7a1f92a4a26154
parent ba574911f617033a26b0e10ecc8010db6f2dc398
Author: Nicolas Silva <nical@fastmail.com>
Date: Fri, 12 Dec 2025 14:44:32 +0000
Bug 1998913 - Part 2 - Extract dependency tracking and quadtree. r=gfx-reviewers,gw
Differential Revision: https://phabricator.services.mozilla.com/D275937
Diffstat:
4 files changed, 884 insertions(+), 828 deletions(-)
diff --git a/gfx/wr/webrender/src/invalidation/dependency.rs b/gfx/wr/webrender/src/invalidation/dependency.rs
@@ -0,0 +1,425 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Dependency tracking for tile invalidation
+//!
+//! This module contains types and logic for tracking dependencies that affect
+//! tile invalidation, including transform comparisons, spatial node tracking,
+//! and primitive comparison.
+
+use api::{ImageKey, PropertyBindingId, ColorU};
+use euclid::approxeq::ApproxEq;
+use crate::PrimitiveCompareResult;
+use crate::spatial_tree::{SpatialTree, SpatialNodeIndex, CoordinateSpaceMapping};
+use crate::internal_types::{FastHashMap, FastHashSet, FrameId};
+use crate::intern::ItemUid;
+use crate::resource_cache::{ResourceCache, ImageGeneration};
+use crate::tile_cache::{TileDescriptor, PrimitiveDescriptor, PrimitiveDependencyIndex};
+use peek_poke::{PeekPoke, peek_from_slice};
+use std::collections::hash_map::Entry;
+
+/// A comparable transform matrix, that compares with epsilon checks.
+#[derive(Debug, Clone)]
+pub struct MatrixKey {
+ pub m: [f32; 16],
+}
+
+impl PartialEq for MatrixKey {
+ fn eq(&self, other: &Self) -> bool {
+ const EPSILON: f32 = 0.001;
+
+ // TODO(gw): It's possible that we may need to adjust the epsilon
+ // to be tighter on most of the matrix, except the
+ // translation parts?
+ for (i, j) in self.m.iter().zip(other.m.iter()) {
+ if !i.approx_eq_eps(j, &EPSILON) {
+ return false;
+ }
+ }
+
+ true
+ }
+}
+
+/// A comparable scale-offset, that compares with epsilon checks.
+#[derive(Debug, Clone)]
+pub struct ScaleOffsetKey {
+ pub sx: f32,
+ pub sy: f32,
+ pub tx: f32,
+ pub ty: f32,
+}
+
+impl PartialEq for ScaleOffsetKey {
+ fn eq(&self, other: &Self) -> bool {
+ const EPSILON: f32 = 0.001;
+
+ self.sx.approx_eq_eps(&other.sx, &EPSILON) &&
+ self.sy.approx_eq_eps(&other.sy, &EPSILON) &&
+ self.tx.approx_eq_eps(&other.tx, &EPSILON) &&
+ self.ty.approx_eq_eps(&other.ty, &EPSILON)
+ }
+}
+
+/// A comparable / hashable version of a coordinate space mapping. Used to determine
+/// if a transform dependency for a tile has changed.
+#[derive(Debug, PartialEq, Clone)]
+pub enum TransformKey {
+ Local,
+ ScaleOffset {
+ so: ScaleOffsetKey,
+ },
+ Transform {
+ m: MatrixKey,
+ }
+}
+
+impl<Src, Dst> From<CoordinateSpaceMapping<Src, Dst>> for TransformKey {
+ fn from(transform: CoordinateSpaceMapping<Src, Dst>) -> TransformKey {
+ match transform {
+ CoordinateSpaceMapping::Local => {
+ TransformKey::Local
+ }
+ CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => {
+ TransformKey::ScaleOffset {
+ so: ScaleOffsetKey {
+ sx: scale_offset.scale.x,
+ sy: scale_offset.scale.y,
+ tx: scale_offset.offset.x,
+ ty: scale_offset.offset.y,
+ }
+ }
+ }
+ CoordinateSpaceMapping::Transform(ref m) => {
+ TransformKey::Transform {
+ m: MatrixKey {
+ m: m.to_array(),
+ },
+ }
+ }
+ }
+ }
+}
+
+/// Get the transform key for a spatial node relative to a cache spatial node.
+pub fn get_transform_key(
+ spatial_node_index: SpatialNodeIndex,
+ cache_spatial_node_index: SpatialNodeIndex,
+ spatial_tree: &SpatialTree,
+) -> TransformKey {
+ spatial_tree.get_relative_transform(
+ spatial_node_index,
+ cache_spatial_node_index,
+ ).into()
+}
+
+
+/// Information about the state of a binding.
+#[derive(Debug)]
+pub struct BindingInfo<T> {
+ /// The current value retrieved from dynamic scene properties.
+ pub value: T,
+ /// True if it was changed (or is new) since the last frame build.
+ pub changed: bool,
+}
+
+/// Information stored in a tile descriptor for a binding.
+#[derive(Debug, PartialEq, Clone, Copy, PeekPoke)]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub enum Binding<T> {
+ Value(T),
+ Binding(PropertyBindingId),
+}
+
+impl<T: Default> Default for Binding<T> {
+ fn default() -> Self {
+ Binding::Value(T::default())
+ }
+}
+
+impl<T> From<api::PropertyBinding<T>> for Binding<T> {
+ fn from(binding: api::PropertyBinding<T>) -> Binding<T> {
+ match binding {
+ api::PropertyBinding::Binding(key, _) => Binding::Binding(key.id),
+ api::PropertyBinding::Value(value) => Binding::Value(value),
+ }
+ }
+}
+
+pub type OpacityBinding = Binding<f32>;
+pub type OpacityBindingInfo = BindingInfo<f32>;
+
+pub type ColorBinding = Binding<ColorU>;
+pub type ColorBindingInfo = BindingInfo<ColorU>;
+
+/// Types of dependencies that a primitive can have
+#[derive(PeekPoke)]
+pub enum PrimitiveDependency {
+ OpacityBinding {
+ binding: OpacityBinding,
+ },
+ ColorBinding {
+ binding: ColorBinding,
+ },
+ SpatialNode {
+ index: SpatialNodeIndex,
+ },
+ Clip {
+ clip: ItemUid,
+ },
+ Image {
+ image: ImageDependency,
+ },
+}
+
+/// Information stored an image dependency
+#[derive(Debug, Copy, Clone, PartialEq, PeekPoke, Default)]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub struct ImageDependency {
+ pub key: ImageKey,
+ pub generation: ImageGeneration,
+}
+
+impl ImageDependency {
+ pub const INVALID: ImageDependency = ImageDependency {
+ key: ImageKey::DUMMY,
+ generation: ImageGeneration::INVALID,
+ };
+}
+
+/// A dependency for a transform is defined by the spatial node index + frame it was used
+#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, PeekPoke, Default)]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub struct SpatialNodeKey {
+ pub spatial_node_index: SpatialNodeIndex,
+ pub frame_id: FrameId,
+}
+
+/// A helper for comparing spatial nodes between frames. The comparisons
+/// are done by-value, so that if the shape of the spatial node tree
+/// changes, invalidations aren't done simply due to the spatial node
+/// index changing between display lists.
+pub struct SpatialNodeComparer {
+ /// The root spatial node index of the tile cache
+ ref_spatial_node_index: SpatialNodeIndex,
+ /// Maintains a map of currently active transform keys
+ spatial_nodes: FastHashMap<SpatialNodeKey, TransformKey>,
+ /// A cache of recent comparisons between prev and current spatial nodes
+ compare_cache: FastHashMap<(SpatialNodeKey, SpatialNodeKey), bool>,
+ /// A set of frames that we need to retain spatial node entries for
+ referenced_frames: FastHashSet<FrameId>,
+}
+
+impl SpatialNodeComparer {
+ /// Construct a new comparer
+ pub fn new() -> Self {
+ SpatialNodeComparer {
+ ref_spatial_node_index: SpatialNodeIndex::INVALID,
+ spatial_nodes: FastHashMap::default(),
+ compare_cache: FastHashMap::default(),
+ referenced_frames: FastHashSet::default(),
+ }
+ }
+
+ /// Advance to the next frame
+ pub fn next_frame(
+ &mut self,
+ ref_spatial_node_index: SpatialNodeIndex,
+ ) {
+ // Drop any node information for unreferenced frames, to ensure that the
+ // hashmap doesn't grow indefinitely!
+ let referenced_frames = &self.referenced_frames;
+ self.spatial_nodes.retain(|key, _| {
+ referenced_frames.contains(&key.frame_id)
+ });
+
+ // Update the root spatial node for this comparer
+ self.ref_spatial_node_index = ref_spatial_node_index;
+ self.compare_cache.clear();
+ self.referenced_frames.clear();
+ }
+
+ /// Register a transform that is used, and build the transform key for it if new.
+ pub fn register_used_transform(
+ &mut self,
+ spatial_node_index: SpatialNodeIndex,
+ frame_id: FrameId,
+ spatial_tree: &SpatialTree,
+ ) {
+ let key = SpatialNodeKey {
+ spatial_node_index,
+ frame_id,
+ };
+
+ if let Entry::Vacant(entry) = self.spatial_nodes.entry(key) {
+ entry.insert(
+ get_transform_key(
+ spatial_node_index,
+ self.ref_spatial_node_index,
+ spatial_tree,
+ )
+ );
+ }
+ }
+
+ /// Return true if the transforms for two given spatial nodes are considered equivalent
+ pub fn are_transforms_equivalent(
+ &mut self,
+ prev_spatial_node_key: &SpatialNodeKey,
+ curr_spatial_node_key: &SpatialNodeKey,
+ ) -> bool {
+ let key = (*prev_spatial_node_key, *curr_spatial_node_key);
+ let spatial_nodes = &self.spatial_nodes;
+
+ *self.compare_cache
+ .entry(key)
+ .or_insert_with(|| {
+ let prev = &spatial_nodes[&prev_spatial_node_key];
+ let curr = &spatial_nodes[&curr_spatial_node_key];
+ curr == prev
+ })
+ }
+
+ /// Ensure that the comparer won't GC any nodes for a given frame id
+ pub fn retain_for_frame(&mut self, frame_id: FrameId) {
+ self.referenced_frames.insert(frame_id);
+ }
+}
+
+
+/// A key for storing primitive comparison results during tile dependency tests.
+#[derive(Debug, Copy, Clone, Eq, Hash, PartialEq)]
+pub struct PrimitiveComparisonKey {
+ pub prev_index: PrimitiveDependencyIndex,
+ pub curr_index: PrimitiveDependencyIndex,
+}
+
+/// A helper struct to compare a primitive and all its sub-dependencies.
+pub struct PrimitiveComparer<'a> {
+ prev_data: &'a [u8],
+ curr_data: &'a [u8],
+ prev_frame_id: FrameId,
+ curr_frame_id: FrameId,
+ resource_cache: &'a ResourceCache,
+ spatial_node_comparer: &'a mut SpatialNodeComparer,
+ opacity_bindings: &'a FastHashMap<PropertyBindingId, OpacityBindingInfo>,
+ color_bindings: &'a FastHashMap<PropertyBindingId, ColorBindingInfo>,
+}
+
+impl<'a> PrimitiveComparer<'a> {
+ pub fn new(
+ prev: &'a TileDescriptor,
+ curr: &'a TileDescriptor,
+ resource_cache: &'a ResourceCache,
+ spatial_node_comparer: &'a mut SpatialNodeComparer,
+ opacity_bindings: &'a FastHashMap<PropertyBindingId, OpacityBindingInfo>,
+ color_bindings: &'a FastHashMap<PropertyBindingId, ColorBindingInfo>,
+ ) -> Self {
+ PrimitiveComparer {
+ prev_data: &prev.dep_data,
+ curr_data: &curr.dep_data,
+ prev_frame_id: prev.last_updated_frame_id,
+ curr_frame_id: curr.last_updated_frame_id,
+ resource_cache,
+ spatial_node_comparer,
+ opacity_bindings,
+ color_bindings,
+ }
+ }
+
+ /// Check if two primitive descriptors are the same.
+ pub fn compare_prim(
+ &mut self,
+ prev_desc: &PrimitiveDescriptor,
+ curr_desc: &PrimitiveDescriptor,
+ ) -> PrimitiveCompareResult {
+ let resource_cache = self.resource_cache;
+ let spatial_node_comparer = &mut self.spatial_node_comparer;
+ let opacity_bindings = self.opacity_bindings;
+ let color_bindings = self.color_bindings;
+
+ // Check equality of the PrimitiveDescriptor
+ if prev_desc != curr_desc {
+ return PrimitiveCompareResult::Descriptor;
+ }
+
+ let mut prev_dep_data = &self.prev_data[prev_desc.dep_offset as usize ..];
+ let mut curr_dep_data = &self.curr_data[curr_desc.dep_offset as usize ..];
+
+ let mut prev_dep = PrimitiveDependency::SpatialNode { index: SpatialNodeIndex::INVALID };
+ let mut curr_dep = PrimitiveDependency::SpatialNode { index: SpatialNodeIndex::INVALID };
+
+ debug_assert_eq!(prev_desc.dep_count, curr_desc.dep_count);
+
+ for _ in 0 .. prev_desc.dep_count {
+ prev_dep_data = peek_from_slice(prev_dep_data, &mut prev_dep);
+ curr_dep_data = peek_from_slice(curr_dep_data, &mut curr_dep);
+
+ match (&prev_dep, &curr_dep) {
+ (PrimitiveDependency::Clip { clip: prev }, PrimitiveDependency::Clip { clip: curr }) => {
+ if prev != curr {
+ return PrimitiveCompareResult::Clip;
+ }
+ }
+ (PrimitiveDependency::SpatialNode { index: prev }, PrimitiveDependency::SpatialNode { index: curr }) => {
+ let prev_key = SpatialNodeKey {
+ spatial_node_index: *prev,
+ frame_id: self.prev_frame_id,
+ };
+ let curr_key = SpatialNodeKey {
+ spatial_node_index: *curr,
+ frame_id: self.curr_frame_id,
+ };
+ if !spatial_node_comparer.are_transforms_equivalent(&prev_key, &curr_key) {
+ return PrimitiveCompareResult::Transform;
+ }
+ }
+ (PrimitiveDependency::OpacityBinding { binding: prev }, PrimitiveDependency::OpacityBinding { binding: curr }) => {
+ if prev != curr {
+ return PrimitiveCompareResult::OpacityBinding;
+ }
+
+ if let OpacityBinding::Binding(id) = curr {
+ if opacity_bindings
+ .get(id)
+ .map_or(true, |info| info.changed) {
+ return PrimitiveCompareResult::OpacityBinding;
+ }
+ }
+ }
+ (PrimitiveDependency::ColorBinding { binding: prev }, PrimitiveDependency::ColorBinding { binding: curr }) => {
+ if prev != curr {
+ return PrimitiveCompareResult::ColorBinding;
+ }
+
+ if let ColorBinding::Binding(id) = curr {
+ if color_bindings
+ .get(id)
+ .map_or(true, |info| info.changed) {
+ return PrimitiveCompareResult::ColorBinding;
+ }
+ }
+ }
+ (PrimitiveDependency::Image { image: prev }, PrimitiveDependency::Image { image: curr }) => {
+ if prev != curr {
+ return PrimitiveCompareResult::Image;
+ }
+
+ if resource_cache.get_image_generation(curr.key) != curr.generation {
+ return PrimitiveCompareResult::Image;
+ }
+ }
+ _ => {
+ // There was a mismatch between types of dependencies, so something changed
+ return PrimitiveCompareResult::Descriptor;
+ }
+ }
+ }
+
+ PrimitiveCompareResult::Equal
+ }
+}
diff --git a/gfx/wr/webrender/src/invalidation/mod.rs b/gfx/wr/webrender/src/invalidation/mod.rs
@@ -7,6 +7,9 @@
//! This module contains types and logic for tracking dirty regions and
//! dependencies used to determine what needs to be redrawn each frame.
+pub mod dependency;
+pub mod quadtree;
+
use api::units::*;
use crate::spatial_tree::{SpatialTree, SpatialNodeIndex};
use crate::space::SpaceMapper;
diff --git a/gfx/wr/webrender/src/invalidation/quadtree.rs b/gfx/wr/webrender/src/invalidation/quadtree.rs
@@ -0,0 +1,440 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Quadtree-based dirty region tracking for tiles
+//!
+//! This module implements a quadtree data structure that tracks which regions
+//! of a tile have been invalidated. The quadtree can dynamically split and merge
+//! nodes based on invalidation patterns to optimize tracking.
+
+use api::units::*;
+use crate::debug_colors;
+use crate::internal_types::FastHashMap;
+use crate::prim_store::PrimitiveScratchBuffer;
+use crate::space::SpaceMapper;
+use crate::tile_cache::{PrimitiveDescriptor, PrimitiveDependencyIndex};
+use crate::invalidation::{InvalidationReason, PrimitiveCompareResult};
+use crate::invalidation::dependency::PrimitiveComparer;
+use crate::visibility::FrameVisibilityContext;
+use std::mem;
+
+
+/// Details for a node in a quadtree that tracks dirty rects for a tile.
+#[cfg_attr(any(feature="capture",feature="replay"), derive(Clone))]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub enum TileNodeKind {
+ Leaf {
+ /// The index buffer of primitives that affected this tile previous frame
+ #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
+ prev_indices: Vec<PrimitiveDependencyIndex>,
+ /// The index buffer of primitives that affect this tile on this frame
+ #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
+ curr_indices: Vec<PrimitiveDependencyIndex>,
+ /// A bitset of which of the last 64 frames have been dirty for this leaf.
+ #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
+ dirty_tracker: u64,
+ /// The number of frames since this node split or merged.
+ #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
+ frames_since_modified: usize,
+ },
+ Node {
+ /// The four children of this node
+ children: Vec<TileNode>,
+ },
+}
+
+/// The kind of modification that a tile wants to do
+#[derive(Copy, Clone, PartialEq, Debug)]
+enum TileModification {
+ Split,
+ Merge,
+}
+
+/// A node in the dirty rect tracking quadtree.
+#[cfg_attr(any(feature="capture",feature="replay"), derive(Clone))]
+#[cfg_attr(feature = "capture", derive(Serialize))]
+#[cfg_attr(feature = "replay", derive(Deserialize))]
+pub struct TileNode {
+ /// Leaf or internal node
+ pub kind: TileNodeKind,
+ /// Rect of this node in the same space as the tile cache picture
+ pub rect: PictureBox2D,
+}
+
+impl TileNode {
+ /// Construct a new leaf node, with the given primitive dependency index buffer
+ pub fn new_leaf(curr_indices: Vec<PrimitiveDependencyIndex>) -> Self {
+ TileNode {
+ kind: TileNodeKind::Leaf {
+ prev_indices: Vec::new(),
+ curr_indices,
+ dirty_tracker: 0,
+ frames_since_modified: 0,
+ },
+ rect: PictureBox2D::zero(),
+ }
+ }
+
+ /// Draw debug information about this tile node
+ pub fn draw_debug_rects(
+ &self,
+ pic_to_world_mapper: &SpaceMapper<PicturePixel, WorldPixel>,
+ is_opaque: bool,
+ local_valid_rect: PictureRect,
+ scratch: &mut PrimitiveScratchBuffer,
+ global_device_pixel_scale: DevicePixelScale,
+ ) {
+ match self.kind {
+ TileNodeKind::Leaf { dirty_tracker, .. } => {
+ let color = if (dirty_tracker & 1) != 0 {
+ debug_colors::RED
+ } else if is_opaque {
+ debug_colors::GREEN
+ } else {
+ debug_colors::YELLOW
+ };
+
+ if let Some(local_rect) = local_valid_rect.intersection(&self.rect) {
+ let world_rect = pic_to_world_mapper
+ .map(&local_rect)
+ .unwrap();
+ let device_rect = world_rect * global_device_pixel_scale;
+
+ let outer_color = color.scale_alpha(0.3);
+ let inner_color = outer_color.scale_alpha(0.5);
+ scratch.push_debug_rect(
+ device_rect.inflate(-3.0, -3.0),
+ 1,
+ outer_color,
+ inner_color
+ );
+ }
+ }
+ TileNodeKind::Node { ref children, .. } => {
+ for child in children.iter() {
+ child.draw_debug_rects(
+ pic_to_world_mapper,
+ is_opaque,
+ local_valid_rect,
+ scratch,
+ global_device_pixel_scale,
+ );
+ }
+ }
+ }
+ }
+
+ /// Calculate the four child rects for a given node
+ fn get_child_rects(
+ rect: &PictureBox2D,
+ result: &mut [PictureBox2D; 4],
+ ) {
+ let p0 = rect.min;
+ let p1 = rect.max;
+ let pc = p0 + rect.size() * 0.5;
+
+ *result = [
+ PictureBox2D::new(
+ p0,
+ pc,
+ ),
+ PictureBox2D::new(
+ PicturePoint::new(pc.x, p0.y),
+ PicturePoint::new(p1.x, pc.y),
+ ),
+ PictureBox2D::new(
+ PicturePoint::new(p0.x, pc.y),
+ PicturePoint::new(pc.x, p1.y),
+ ),
+ PictureBox2D::new(
+ pc,
+ p1,
+ ),
+ ];
+ }
+
+ /// Called during pre_update, to clear the current dependencies
+ pub fn clear(
+ &mut self,
+ rect: PictureBox2D,
+ ) {
+ self.rect = rect;
+
+ match self.kind {
+ TileNodeKind::Leaf { ref mut prev_indices, ref mut curr_indices, ref mut dirty_tracker, ref mut frames_since_modified } => {
+ // Swap current dependencies to be the previous frame
+ mem::swap(prev_indices, curr_indices);
+ curr_indices.clear();
+ // Note that another frame has passed in the dirty bit trackers
+ *dirty_tracker = *dirty_tracker << 1;
+ *frames_since_modified += 1;
+ }
+ TileNodeKind::Node { ref mut children, .. } => {
+ let mut child_rects = [PictureBox2D::zero(); 4];
+ TileNode::get_child_rects(&rect, &mut child_rects);
+ assert_eq!(child_rects.len(), children.len());
+
+ for (child, rect) in children.iter_mut().zip(child_rects.iter()) {
+ child.clear(*rect);
+ }
+ }
+ }
+ }
+
+ /// Add a primitive dependency to this node
+ pub fn add_prim(
+ &mut self,
+ index: PrimitiveDependencyIndex,
+ prim_rect: &PictureBox2D,
+ ) {
+ match self.kind {
+ TileNodeKind::Leaf { ref mut curr_indices, .. } => {
+ curr_indices.push(index);
+ }
+ TileNodeKind::Node { ref mut children, .. } => {
+ for child in children.iter_mut() {
+ if child.rect.intersects(prim_rect) {
+ child.add_prim(index, prim_rect);
+ }
+ }
+ }
+ }
+ }
+
+ /// Apply a merge or split operation to this tile, if desired
+ pub fn maybe_merge_or_split(
+ &mut self,
+ level: i32,
+ curr_prims: &[PrimitiveDescriptor],
+ max_split_levels: i32,
+ ) {
+ // Determine if this tile wants to split or merge
+ let mut tile_mod = None;
+
+ fn get_dirty_frames(
+ dirty_tracker: u64,
+ frames_since_modified: usize,
+ ) -> Option<u32> {
+ // Only consider splitting or merging at least 64 frames since we last changed
+ if frames_since_modified > 64 {
+ // Each bit in the tracker is a frame that was recently invalidated
+ Some(dirty_tracker.count_ones())
+ } else {
+ None
+ }
+ }
+
+ match self.kind {
+ TileNodeKind::Leaf { dirty_tracker, frames_since_modified, .. } => {
+ // Only consider splitting if the tree isn't too deep.
+ if level < max_split_levels {
+ if let Some(dirty_frames) = get_dirty_frames(dirty_tracker, frames_since_modified) {
+ // If the tile has invalidated > 50% of the recent number of frames, split.
+ if dirty_frames > 32 {
+ tile_mod = Some(TileModification::Split);
+ }
+ }
+ }
+ }
+ TileNodeKind::Node { ref children, .. } => {
+ // There's two conditions that cause a node to merge its children:
+ // (1) If _all_ the child nodes are constantly invalidating, then we are wasting
+ // CPU time tracking dependencies for each child, so merge them.
+ // (2) If _none_ of the child nodes are recently invalid, then the page content
+ // has probably changed, and we no longer need to track fine grained dependencies here.
+
+ let mut static_count = 0;
+ let mut changing_count = 0;
+
+ for child in children {
+ // Only consider merging nodes at the edge of the tree.
+ if let TileNodeKind::Leaf { dirty_tracker, frames_since_modified, .. } = child.kind {
+ if let Some(dirty_frames) = get_dirty_frames(dirty_tracker, frames_since_modified) {
+ if dirty_frames == 0 {
+ // Hasn't been invalidated for some time
+ static_count += 1;
+ } else if dirty_frames == 64 {
+ // Is constantly being invalidated
+ changing_count += 1;
+ }
+ }
+ }
+
+ // Only merge if all the child tiles are in agreement. Otherwise, we have some
+ // that are invalidating / static, and it's worthwhile tracking dependencies for
+ // them individually.
+ if static_count == 4 || changing_count == 4 {
+ tile_mod = Some(TileModification::Merge);
+ }
+ }
+ }
+ }
+
+ match tile_mod {
+ Some(TileModification::Split) => {
+ // To split a node, take the current dependency index buffer for this node, and
+ // split it into child index buffers.
+ let curr_indices = match self.kind {
+ TileNodeKind::Node { .. } => {
+ unreachable!("bug - only leaves can split");
+ }
+ TileNodeKind::Leaf { ref mut curr_indices, .. } => {
+ mem::take(curr_indices)
+ }
+ };
+
+ let mut child_rects = [PictureBox2D::zero(); 4];
+ TileNode::get_child_rects(&self.rect, &mut child_rects);
+
+ let mut child_indices = [
+ Vec::new(),
+ Vec::new(),
+ Vec::new(),
+ Vec::new(),
+ ];
+
+ // Step through the index buffer, and add primitives to each of the children
+ // that they intersect.
+ for index in curr_indices {
+ let prim = &curr_prims[index.0 as usize];
+ for (child_rect, indices) in child_rects.iter().zip(child_indices.iter_mut()) {
+ if prim.prim_clip_box.intersects(child_rect) {
+ indices.push(index);
+ }
+ }
+ }
+
+ // Create the child nodes and switch from leaf -> node.
+ let children = child_indices
+ .iter_mut()
+ .map(|i| TileNode::new_leaf(mem::replace(i, Vec::new())))
+ .collect();
+
+ self.kind = TileNodeKind::Node {
+ children,
+ };
+ }
+ Some(TileModification::Merge) => {
+ // Construct a merged index buffer by collecting the dependency index buffers
+ // from each child, and merging them into a de-duplicated index buffer.
+ let merged_indices = match self.kind {
+ TileNodeKind::Node { ref mut children, .. } => {
+ let mut merged_indices = Vec::new();
+
+ for child in children.iter() {
+ let child_indices = match child.kind {
+ TileNodeKind::Leaf { ref curr_indices, .. } => {
+ curr_indices
+ }
+ TileNodeKind::Node { .. } => {
+ unreachable!("bug: child is not a leaf");
+ }
+ };
+ merged_indices.extend_from_slice(child_indices);
+ }
+
+ merged_indices.sort();
+ merged_indices.dedup();
+
+ merged_indices
+ }
+ TileNodeKind::Leaf { .. } => {
+ unreachable!("bug - trying to merge a leaf");
+ }
+ };
+
+ // Switch from a node to a leaf, with the combined index buffer
+ self.kind = TileNodeKind::Leaf {
+ prev_indices: Vec::new(),
+ curr_indices: merged_indices,
+ dirty_tracker: 0,
+ frames_since_modified: 0,
+ };
+ }
+ None => {
+ // If this node didn't merge / split, then recurse into children
+ // to see if they want to split / merge.
+ if let TileNodeKind::Node { ref mut children, .. } = self.kind {
+ for child in children.iter_mut() {
+ child.maybe_merge_or_split(
+ level+1,
+ curr_prims,
+ max_split_levels,
+ );
+ }
+ }
+ }
+ }
+ }
+
+ /// Update the dirty state of this node, building the overall dirty rect
+ pub fn update_dirty_rects(
+ &mut self,
+ prev_prims: &[PrimitiveDescriptor],
+ curr_prims: &[PrimitiveDescriptor],
+ prim_comparer: &mut PrimitiveComparer,
+ dirty_rect: &mut PictureBox2D,
+ compare_cache: &mut FastHashMap<crate::invalidation::dependency::PrimitiveComparisonKey, PrimitiveCompareResult>,
+ invalidation_reason: &mut Option<InvalidationReason>,
+ frame_context: &FrameVisibilityContext,
+ ) {
+ match self.kind {
+ TileNodeKind::Node { ref mut children, .. } => {
+ for child in children.iter_mut() {
+ child.update_dirty_rects(
+ prev_prims,
+ curr_prims,
+ prim_comparer,
+ dirty_rect,
+ compare_cache,
+ invalidation_reason,
+ frame_context,
+ );
+ }
+ }
+ TileNodeKind::Leaf { ref prev_indices, ref curr_indices, ref mut dirty_tracker, .. } => {
+ // If the index buffers are of different length, they must be different
+ if prev_indices.len() == curr_indices.len() {
+ // Walk each index buffer, comparing primitives
+ for (prev_index, curr_index) in prev_indices.iter().zip(curr_indices.iter()) {
+ let i0 = prev_index.0 as usize;
+ let i1 = curr_index.0 as usize;
+
+ // Compare the primitives, caching the result in a hash map
+ // to save comparisons in other tree nodes.
+ let key = crate::invalidation::dependency::PrimitiveComparisonKey {
+ prev_index: *prev_index,
+ curr_index: *curr_index,
+ };
+
+ let prim_compare_result = *compare_cache
+ .entry(key)
+ .or_insert_with(|| {
+ let prev = &prev_prims[i0];
+ let curr = &curr_prims[i1];
+ prim_comparer.compare_prim(prev, curr)
+ });
+
+ // If not the same, mark this node as dirty and update the dirty rect
+ if prim_compare_result != PrimitiveCompareResult::Equal {
+ if invalidation_reason.is_none() {
+ *invalidation_reason = Some(InvalidationReason::Content);
+ }
+ *dirty_rect = self.rect.union(dirty_rect);
+ *dirty_tracker = *dirty_tracker | 1;
+ break;
+ }
+ }
+ } else {
+ if invalidation_reason.is_none() {
+ *invalidation_reason = Some(InvalidationReason::PrimCount);
+ }
+ *dirty_rect = self.rect.union(dirty_rect);
+ *dirty_tracker = *dirty_tracker | 1;
+ }
+ }
+ }
+ }
+}
diff --git a/gfx/wr/webrender/src/picture.rs b/gfx/wr/webrender/src/picture.rs
@@ -95,8 +95,8 @@
//! improved as a follow up).
use api::{BorderRadius, ClipMode, MixBlendMode, PremultipliedColorF, SVGFE_GRAPH_MAX};
-use api::{PropertyBinding, PropertyBindingId, FilterOpGraphPictureBufferId, RasterSpace};
-use api::{DebugFlags, ImageKey, ColorF, ColorU, PrimitiveFlags, SnapshotInfo};
+use api::{PropertyBindingId, FilterOpGraphPictureBufferId, RasterSpace};
+use api::{DebugFlags, ImageKey, ColorF, PrimitiveFlags, SnapshotInfo};
use api::{ImageRendering, ColorDepth, YuvRangedColorSpace, YuvFormat, AlphaType};
use api::units::*;
use crate::prim_store::image::AdjustedImageSource;
@@ -112,11 +112,11 @@ use crate::debug_colors;
use euclid::{vec3, Scale, Vector2D, Box2D};
use euclid::approxeq::ApproxEq;
use crate::intern::ItemUid;
-use crate::internal_types::{FastHashMap, FastHashSet, PlaneSplitter, FilterGraphOp, FilterGraphNode, Filter, FrameId};
+use crate::internal_types::{FastHashMap, PlaneSplitter, FilterGraphOp, FilterGraphNode, Filter, FrameId};
use crate::internal_types::{PlaneSplitterIndex, PlaneSplitAnchor, TextureSource};
use crate::frame_builder::{FrameBuildingContext, FrameBuildingState, PictureState, PictureContext};
-use crate::gpu_types::{BlurEdgeMode, BrushSegmentGpuData, ImageBrushPrimitiveData, UvRectKind, ZBufferId};
-use peek_poke::{PeekPoke, poke_into_vec, peek_from_slice, ensure_red_zone};
+use crate::gpu_types::{UvRectKind, ZBufferId, BlurEdgeMode, BrushSegmentGpuData, ImageBrushPrimitiveData};
+use peek_poke::{poke_into_vec, ensure_red_zone};
use plane_split::{Clipper, Polygon};
use crate::prim_store::{PrimitiveTemplateKind, PictureIndex, PrimitiveInstance, PrimitiveInstanceKind};
use crate::prim_store::{ColorBindingStorage, ColorBindingIndex, PrimitiveScratchBuffer};
@@ -127,7 +127,7 @@ use crate::render_target::RenderTargetKind;
use crate::render_task::{BlurTask, RenderTask, RenderTaskLocation, BlurTaskCache};
use crate::render_task::{StaticRenderTaskSurface, RenderTaskKind};
use crate::renderer::{BlendMode, GpuBufferAddress};
-use crate::resource_cache::{ResourceCache, ImageGeneration, ImageRequest};
+use crate::resource_cache::{ResourceCache, ImageRequest};
use crate::space::SpaceMapper;
use crate::scene::SceneProperties;
use crate::spatial_tree::CoordinateSystemId;
@@ -135,10 +135,9 @@ use crate::surface::{SurfaceDescriptor, SurfaceTileDescriptor};
use smallvec::SmallVec;
use std::{mem, u8, u32};
use std::fmt::{Display, Error, Formatter};
-use std::collections::hash_map::Entry;
use std::ops::Range;
use crate::picture_textures::PictureCacheTextureHandle;
-use crate::util::{MaxRect, VecHelper, MatrixHelpers, Recycler, ScaleOffset};
+use crate::util::{MaxRect, MatrixHelpers, Recycler, ScaleOffset};
use crate::filterdata::FilterDataHandle;
use crate::tile_cache::{SliceDebugInfo, TileDebugInfo, DirtyTileDebugInfo};
use crate::tile_cache::{TileKey, TileId, TileRect, TileOffset, SubSliceIndex};
@@ -152,6 +151,15 @@ use crate::scene_building::SliceFlags;
use core::time::Duration;
pub use crate::invalidation::DirtyRegion;
+pub use crate::invalidation::dependency::ImageDependency;
+pub use crate::invalidation::quadtree::{TileNode, TileNodeKind};
+use crate::invalidation::dependency::{
+ OpacityBindingInfo, ColorBindingInfo,
+ OpacityBinding, ColorBinding,
+ PrimitiveDependency,
+ SpatialNodeComparer,
+ PrimitiveComparisonKey, PrimitiveComparer,
+};
use crate::invalidation::PrimitiveCompareResult;
@@ -174,89 +182,6 @@ pub enum SubpixelMode {
},
}
-/// A comparable transform matrix, that compares with epsilon checks.
-#[derive(Debug, Clone)]
-struct MatrixKey {
- m: [f32; 16],
-}
-
-impl PartialEq for MatrixKey {
- fn eq(&self, other: &Self) -> bool {
- const EPSILON: f32 = 0.001;
-
- // TODO(gw): It's possible that we may need to adjust the epsilon
- // to be tighter on most of the matrix, except the
- // translation parts?
- for (i, j) in self.m.iter().zip(other.m.iter()) {
- if !i.approx_eq_eps(j, &EPSILON) {
- return false;
- }
- }
-
- true
- }
-}
-
-/// A comparable scale-offset, that compares with epsilon checks.
-#[derive(Debug, Clone)]
-struct ScaleOffsetKey {
- sx: f32,
- sy: f32,
- tx: f32,
- ty: f32,
-}
-
-impl PartialEq for ScaleOffsetKey {
- fn eq(&self, other: &Self) -> bool {
- const EPSILON: f32 = 0.001;
-
- self.sx.approx_eq_eps(&other.sx, &EPSILON) &&
- self.sy.approx_eq_eps(&other.sy, &EPSILON) &&
- self.tx.approx_eq_eps(&other.tx, &EPSILON) &&
- self.ty.approx_eq_eps(&other.ty, &EPSILON)
- }
-}
-
-/// A comparable / hashable version of a coordinate space mapping. Used to determine
-/// if a transform dependency for a tile has changed.
-#[derive(Debug, PartialEq, Clone)]
-enum TransformKey {
- Local,
- ScaleOffset {
- so: ScaleOffsetKey,
- },
- Transform {
- m: MatrixKey,
- }
-}
-
-impl<Src, Dst> From<CoordinateSpaceMapping<Src, Dst>> for TransformKey {
- fn from(transform: CoordinateSpaceMapping<Src, Dst>) -> TransformKey {
- match transform {
- CoordinateSpaceMapping::Local => {
- TransformKey::Local
- }
- CoordinateSpaceMapping::ScaleOffset(ref scale_offset) => {
- TransformKey::ScaleOffset {
- so: ScaleOffsetKey {
- sx: scale_offset.scale.x,
- sy: scale_offset.scale.y,
- tx: scale_offset.offset.x,
- ty: scale_offset.offset.y,
- }
- }
- }
- CoordinateSpaceMapping::Transform(ref m) => {
- TransformKey::Transform {
- m: MatrixKey {
- m: m.to_array(),
- },
- }
- }
- }
- }
-}
-
/// Maximum size of a compositor surface.
const MAX_COMPOSITOR_SURFACES_SIZE: f32 = 8192.0;
@@ -268,164 +193,6 @@ fn clampf(value: f32, low: f32, high: f32) -> f32 {
value.max(low).min(high)
}
-/// Information about the state of a binding.
-#[derive(Debug)]
-pub struct BindingInfo<T> {
- /// The current value retrieved from dynamic scene properties.
- value: T,
- /// True if it was changed (or is new) since the last frame build.
- changed: bool,
-}
-
-/// Information stored in a tile descriptor for a binding.
-#[derive(Debug, PartialEq, Clone, Copy, PeekPoke)]
-#[cfg_attr(feature = "capture", derive(Serialize))]
-#[cfg_attr(feature = "replay", derive(Deserialize))]
-pub enum Binding<T> {
- Value(T),
- Binding(PropertyBindingId),
-}
-
-impl<T: Default> Default for Binding<T> {
- fn default() -> Self {
- Binding::Value(T::default())
- }
-}
-
-impl<T> From<PropertyBinding<T>> for Binding<T> {
- fn from(binding: PropertyBinding<T>) -> Binding<T> {
- match binding {
- PropertyBinding::Binding(key, _) => Binding::Binding(key.id),
- PropertyBinding::Value(value) => Binding::Value(value),
- }
- }
-}
-
-pub type OpacityBinding = Binding<f32>;
-pub type OpacityBindingInfo = BindingInfo<f32>;
-
-pub type ColorBinding = Binding<ColorU>;
-pub type ColorBindingInfo = BindingInfo<ColorU>;
-
-#[derive(PeekPoke)]
-enum PrimitiveDependency {
- OpacityBinding {
- binding: OpacityBinding,
- },
- ColorBinding {
- binding: ColorBinding,
- },
- SpatialNode {
- index: SpatialNodeIndex,
- },
- Clip {
- clip: ItemUid,
- },
- Image {
- image: ImageDependency,
- },
-}
-
-/// A dependency for a transform is defined by the spatial node index + frame it was used
-#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, PeekPoke, Default)]
-#[cfg_attr(feature = "capture", derive(Serialize))]
-#[cfg_attr(feature = "replay", derive(Deserialize))]
-pub struct SpatialNodeKey {
- spatial_node_index: SpatialNodeIndex,
- frame_id: FrameId,
-}
-
-/// A helper for comparing spatial nodes between frames. The comparisons
-/// are done by-value, so that if the shape of the spatial node tree
-/// changes, invalidations aren't done simply due to the spatial node
-/// index changing between display lists.
-struct SpatialNodeComparer {
- /// The root spatial node index of the tile cache
- ref_spatial_node_index: SpatialNodeIndex,
- /// Maintains a map of currently active transform keys
- spatial_nodes: FastHashMap<SpatialNodeKey, TransformKey>,
- /// A cache of recent comparisons between prev and current spatial nodes
- compare_cache: FastHashMap<(SpatialNodeKey, SpatialNodeKey), bool>,
- /// A set of frames that we need to retain spatial node entries for
- referenced_frames: FastHashSet<FrameId>,
-}
-
-impl SpatialNodeComparer {
- /// Construct a new comparer
- fn new() -> Self {
- SpatialNodeComparer {
- ref_spatial_node_index: SpatialNodeIndex::INVALID,
- spatial_nodes: FastHashMap::default(),
- compare_cache: FastHashMap::default(),
- referenced_frames: FastHashSet::default(),
- }
- }
-
- /// Advance to the next frame
- fn next_frame(
- &mut self,
- ref_spatial_node_index: SpatialNodeIndex,
- ) {
- // Drop any node information for unreferenced frames, to ensure that the
- // hashmap doesn't grow indefinitely!
- let referenced_frames = &self.referenced_frames;
- self.spatial_nodes.retain(|key, _| {
- referenced_frames.contains(&key.frame_id)
- });
-
- // Update the root spatial node for this comparer
- self.ref_spatial_node_index = ref_spatial_node_index;
- self.compare_cache.clear();
- self.referenced_frames.clear();
- }
-
- /// Register a transform that is used, and build the transform key for it if new.
- fn register_used_transform(
- &mut self,
- spatial_node_index: SpatialNodeIndex,
- frame_id: FrameId,
- spatial_tree: &SpatialTree,
- ) {
- let key = SpatialNodeKey {
- spatial_node_index,
- frame_id,
- };
-
- if let Entry::Vacant(entry) = self.spatial_nodes.entry(key) {
- entry.insert(
- get_transform_key(
- spatial_node_index,
- self.ref_spatial_node_index,
- spatial_tree,
- )
- );
- }
- }
-
- /// Return true if the transforms for two given spatial nodes are considered equivalent
- fn are_transforms_equivalent(
- &mut self,
- prev_spatial_node_key: &SpatialNodeKey,
- curr_spatial_node_key: &SpatialNodeKey,
- ) -> bool {
- let key = (*prev_spatial_node_key, *curr_spatial_node_key);
- let spatial_nodes = &self.spatial_nodes;
-
- *self.compare_cache
- .entry(key)
- .or_insert_with(|| {
- let prev = &spatial_nodes[&prev_spatial_node_key];
- let curr = &spatial_nodes[&curr_spatial_node_key];
- curr == prev
- })
- }
-
- /// Ensure that the comparer won't GC any nodes for a given frame id
- fn retain_for_frame(&mut self, frame_id: FrameId) {
- self.referenced_frames.insert(frame_id);
- }
-}
-
// Immutable context passed to picture cache tiles during pre_update
struct TilePreUpdateContext {
/// Maps from picture cache coords -> world space coords.
@@ -6970,40 +6737,6 @@ impl PicturePrimitive {
}
}
-fn get_transform_key(
- spatial_node_index: SpatialNodeIndex,
- cache_spatial_node_index: SpatialNodeIndex,
- spatial_tree: &SpatialTree,
-) -> TransformKey {
- spatial_tree.get_relative_transform(
- spatial_node_index,
- cache_spatial_node_index,
- ).into()
-}
-
-/// A key for storing primitive comparison results during tile dependency tests.
-#[derive(Debug, Copy, Clone, Eq, Hash, PartialEq)]
-struct PrimitiveComparisonKey {
- prev_index: PrimitiveDependencyIndex,
- curr_index: PrimitiveDependencyIndex,
-}
-
-/// Information stored an image dependency
-#[derive(Debug, Copy, Clone, PartialEq, PeekPoke, Default)]
-#[cfg_attr(feature = "capture", derive(Serialize))]
-#[cfg_attr(feature = "replay", derive(Deserialize))]
-pub struct ImageDependency {
- pub key: ImageKey,
- pub generation: ImageGeneration,
-}
-
-impl ImageDependency {
- pub const INVALID: ImageDependency = ImageDependency {
- key: ImageKey::DUMMY,
- generation: ImageGeneration::INVALID,
- };
-}
-
/// In some cases, we need to know the dirty rect of all tiles in order
/// to correctly invalidate a primitive.
#[derive(Debug)]
@@ -7014,551 +6747,6 @@ struct DeferredDirtyTest {
prim_rect: PictureRect,
}
-/// A helper struct to compare a primitive and all its sub-dependencies.
-struct PrimitiveComparer<'a> {
- prev_data: &'a [u8],
- curr_data: &'a [u8],
- prev_frame_id: FrameId,
- curr_frame_id: FrameId,
- resource_cache: &'a ResourceCache,
- spatial_node_comparer: &'a mut SpatialNodeComparer,
- opacity_bindings: &'a FastHashMap<PropertyBindingId, OpacityBindingInfo>,
- color_bindings: &'a FastHashMap<PropertyBindingId, ColorBindingInfo>,
-}
-
-impl<'a> PrimitiveComparer<'a> {
- fn new(
- prev: &'a TileDescriptor,
- curr: &'a TileDescriptor,
- resource_cache: &'a ResourceCache,
- spatial_node_comparer: &'a mut SpatialNodeComparer,
- opacity_bindings: &'a FastHashMap<PropertyBindingId, OpacityBindingInfo>,
- color_bindings: &'a FastHashMap<PropertyBindingId, ColorBindingInfo>,
- ) -> Self {
- PrimitiveComparer {
- prev_data: &prev.dep_data,
- curr_data: &curr.dep_data,
- prev_frame_id: prev.last_updated_frame_id,
- curr_frame_id: curr.last_updated_frame_id,
- resource_cache,
- spatial_node_comparer,
- opacity_bindings,
- color_bindings,
- }
- }
-
- /// Check if two primitive descriptors are the same.
- fn compare_prim(
- &mut self,
- prev_desc: &PrimitiveDescriptor,
- curr_desc: &PrimitiveDescriptor,
- ) -> PrimitiveCompareResult {
- let resource_cache = self.resource_cache;
- let spatial_node_comparer = &mut self.spatial_node_comparer;
- let opacity_bindings = self.opacity_bindings;
- let color_bindings = self.color_bindings;
-
- // Check equality of the PrimitiveDescriptor
- if prev_desc != curr_desc {
- return PrimitiveCompareResult::Descriptor;
- }
-
- let mut prev_dep_data = &self.prev_data[prev_desc.dep_offset as usize ..];
- let mut curr_dep_data = &self.curr_data[curr_desc.dep_offset as usize ..];
-
- let mut prev_dep = PrimitiveDependency::SpatialNode { index: SpatialNodeIndex::INVALID };
- let mut curr_dep = PrimitiveDependency::SpatialNode { index: SpatialNodeIndex::INVALID };
-
- debug_assert_eq!(prev_desc.dep_count, curr_desc.dep_count);
-
- for _ in 0 .. prev_desc.dep_count {
- prev_dep_data = peek_from_slice(prev_dep_data, &mut prev_dep);
- curr_dep_data = peek_from_slice(curr_dep_data, &mut curr_dep);
-
- match (&prev_dep, &curr_dep) {
- (PrimitiveDependency::Clip { clip: prev }, PrimitiveDependency::Clip { clip: curr }) => {
- if prev != curr {
- return PrimitiveCompareResult::Clip;
- }
- }
- (PrimitiveDependency::SpatialNode { index: prev }, PrimitiveDependency::SpatialNode { index: curr }) => {
- let prev_key = SpatialNodeKey {
- spatial_node_index: *prev,
- frame_id: self.prev_frame_id,
- };
- let curr_key = SpatialNodeKey {
- spatial_node_index: *curr,
- frame_id: self.curr_frame_id,
- };
- if !spatial_node_comparer.are_transforms_equivalent(&prev_key, &curr_key) {
- return PrimitiveCompareResult::Transform;
- }
- }
- (PrimitiveDependency::OpacityBinding { binding: prev }, PrimitiveDependency::OpacityBinding { binding: curr }) => {
- if prev != curr {
- return PrimitiveCompareResult::OpacityBinding;
- }
-
- if let OpacityBinding::Binding(id) = curr {
- if opacity_bindings
- .get(id)
- .map_or(true, |info| info.changed) {
- return PrimitiveCompareResult::OpacityBinding;
- }
- }
- }
- (PrimitiveDependency::ColorBinding { binding: prev }, PrimitiveDependency::ColorBinding { binding: curr }) => {
- if prev != curr {
- return PrimitiveCompareResult::ColorBinding;
- }
-
- if let ColorBinding::Binding(id) = curr {
- if color_bindings
- .get(id)
- .map_or(true, |info| info.changed) {
- return PrimitiveCompareResult::ColorBinding;
- }
- }
- }
- (PrimitiveDependency::Image { image: prev }, PrimitiveDependency::Image { image: curr }) => {
- if prev != curr {
- return PrimitiveCompareResult::Image;
- }
-
- if resource_cache.get_image_generation(curr.key) != curr.generation {
- return PrimitiveCompareResult::Image;
- }
- }
- _ => {
- // There was a mismatch between types of dependencies, so something changed
- return PrimitiveCompareResult::Descriptor;
- }
- }
- }
-
- PrimitiveCompareResult::Equal
- }
-}
-
-/// Details for a node in a quadtree that tracks dirty rects for a tile.
-#[cfg_attr(any(feature="capture",feature="replay"), derive(Clone))]
-#[cfg_attr(feature = "capture", derive(Serialize))]
-#[cfg_attr(feature = "replay", derive(Deserialize))]
-pub enum TileNodeKind {
- Leaf {
- /// The index buffer of primitives that affected this tile previous frame
- #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
- prev_indices: Vec<PrimitiveDependencyIndex>,
- /// The index buffer of primitives that affect this tile on this frame
- #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
- curr_indices: Vec<PrimitiveDependencyIndex>,
- /// A bitset of which of the last 64 frames have been dirty for this leaf.
- #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
- dirty_tracker: u64,
- /// The number of frames since this node split or merged.
- #[cfg_attr(any(feature = "capture", feature = "replay"), serde(skip))]
- frames_since_modified: usize,
- },
- Node {
- /// The four children of this node
- children: Vec<TileNode>,
- },
-}
-
-/// The kind of modification that a tile wants to do
-#[derive(Copy, Clone, PartialEq, Debug)]
-enum TileModification {
- Split,
- Merge,
-}
-
-/// A node in the dirty rect tracking quadtree.
-#[cfg_attr(any(feature="capture",feature="replay"), derive(Clone))]
-#[cfg_attr(feature = "capture", derive(Serialize))]
-#[cfg_attr(feature = "replay", derive(Deserialize))]
-pub struct TileNode {
- /// Leaf or internal node
- pub kind: TileNodeKind,
- /// Rect of this node in the same space as the tile cache picture
- pub rect: PictureBox2D,
-}
-
-impl TileNode {
- /// Construct a new leaf node, with the given primitive dependency index buffer
- fn new_leaf(curr_indices: Vec<PrimitiveDependencyIndex>) -> Self {
- TileNode {
- kind: TileNodeKind::Leaf {
- prev_indices: Vec::new(),
- curr_indices,
- dirty_tracker: 0,
- frames_since_modified: 0,
- },
- rect: PictureBox2D::zero(),
- }
- }
-
- /// Draw debug information about this tile node
- fn draw_debug_rects(
- &self,
- pic_to_world_mapper: &SpaceMapper<PicturePixel, WorldPixel>,
- is_opaque: bool,
- local_valid_rect: PictureRect,
- scratch: &mut PrimitiveScratchBuffer,
- global_device_pixel_scale: DevicePixelScale,
- ) {
- match self.kind {
- TileNodeKind::Leaf { dirty_tracker, .. } => {
- let color = if (dirty_tracker & 1) != 0 {
- debug_colors::RED
- } else if is_opaque {
- debug_colors::GREEN
- } else {
- debug_colors::YELLOW
- };
-
- if let Some(local_rect) = local_valid_rect.intersection(&self.rect) {
- let world_rect = pic_to_world_mapper
- .map(&local_rect)
- .unwrap();
- let device_rect = world_rect * global_device_pixel_scale;
-
- let outer_color = color.scale_alpha(0.3);
- let inner_color = outer_color.scale_alpha(0.5);
- scratch.push_debug_rect(
- device_rect.inflate(-3.0, -3.0),
- 1,
- outer_color,
- inner_color
- );
- }
- }
- TileNodeKind::Node { ref children, .. } => {
- for child in children.iter() {
- child.draw_debug_rects(
- pic_to_world_mapper,
- is_opaque,
- local_valid_rect,
- scratch,
- global_device_pixel_scale,
- );
- }
- }
- }
- }
-
- /// Calculate the four child rects for a given node
- fn get_child_rects(
- rect: &PictureBox2D,
- result: &mut [PictureBox2D; 4],
- ) {
- let p0 = rect.min;
- let p1 = rect.max;
- let pc = p0 + rect.size() * 0.5;
-
- *result = [
- PictureBox2D::new(
- p0,
- pc,
- ),
- PictureBox2D::new(
- PicturePoint::new(pc.x, p0.y),
- PicturePoint::new(p1.x, pc.y),
- ),
- PictureBox2D::new(
- PicturePoint::new(p0.x, pc.y),
- PicturePoint::new(pc.x, p1.y),
- ),
- PictureBox2D::new(
- pc,
- p1,
- ),
- ];
- }
-
- /// Called during pre_update, to clear the current dependencies
- fn clear(
- &mut self,
- rect: PictureBox2D,
- ) {
- self.rect = rect;
-
- match self.kind {
- TileNodeKind::Leaf { ref mut prev_indices, ref mut curr_indices, ref mut dirty_tracker, ref mut frames_since_modified } => {
- // Swap current dependencies to be the previous frame
- mem::swap(prev_indices, curr_indices);
- curr_indices.clear();
- // Note that another frame has passed in the dirty bit trackers
- *dirty_tracker = *dirty_tracker << 1;
- *frames_since_modified += 1;
- }
- TileNodeKind::Node { ref mut children, .. } => {
- let mut child_rects = [PictureBox2D::zero(); 4];
- TileNode::get_child_rects(&rect, &mut child_rects);
- assert_eq!(child_rects.len(), children.len());
-
- for (child, rect) in children.iter_mut().zip(child_rects.iter()) {
- child.clear(*rect);
- }
- }
- }
- }
-
- /// Add a primitive dependency to this node
- fn add_prim(
- &mut self,
- index: PrimitiveDependencyIndex,
- prim_rect: &PictureBox2D,
- ) {
- match self.kind {
- TileNodeKind::Leaf { ref mut curr_indices, .. } => {
- curr_indices.push(index);
- }
- TileNodeKind::Node { ref mut children, .. } => {
- for child in children.iter_mut() {
- if child.rect.intersects(prim_rect) {
- child.add_prim(index, prim_rect);
- }
- }
- }
- }
- }
-
- /// Apply a merge or split operation to this tile, if desired
- fn maybe_merge_or_split(
- &mut self,
- level: i32,
- curr_prims: &[PrimitiveDescriptor],
- max_split_levels: i32,
- ) {
- // Determine if this tile wants to split or merge
- let mut tile_mod = None;
-
- fn get_dirty_frames(
- dirty_tracker: u64,
- frames_since_modified: usize,
- ) -> Option<u32> {
- // Only consider splitting or merging at least 64 frames since we last changed
- if frames_since_modified > 64 {
- // Each bit in the tracker is a frame that was recently invalidated
- Some(dirty_tracker.count_ones())
- } else {
- None
- }
- }
-
- match self.kind {
- TileNodeKind::Leaf { dirty_tracker, frames_since_modified, .. } => {
- // Only consider splitting if the tree isn't too deep.
- if level < max_split_levels {
- if let Some(dirty_frames) = get_dirty_frames(dirty_tracker, frames_since_modified) {
- // If the tile has invalidated > 50% of the recent number of frames, split.
- if dirty_frames > 32 {
- tile_mod = Some(TileModification::Split);
- }
- }
- }
- }
- TileNodeKind::Node { ref children, .. } => {
- // There's two conditions that cause a node to merge its children:
- // (1) If _all_ the child nodes are constantly invalidating, then we are wasting
- // CPU time tracking dependencies for each child, so merge them.
- // (2) If _none_ of the child nodes are recently invalid, then the page content
- // has probably changed, and we no longer need to track fine grained dependencies here.
-
- let mut static_count = 0;
- let mut changing_count = 0;
-
- for child in children {
- // Only consider merging nodes at the edge of the tree.
- if let TileNodeKind::Leaf { dirty_tracker, frames_since_modified, .. } = child.kind {
- if let Some(dirty_frames) = get_dirty_frames(dirty_tracker, frames_since_modified) {
- if dirty_frames == 0 {
- // Hasn't been invalidated for some time
- static_count += 1;
- } else if dirty_frames == 64 {
- // Is constantly being invalidated
- changing_count += 1;
- }
- }
- }
-
- // Only merge if all the child tiles are in agreement. Otherwise, we have some
- // that are invalidating / static, and it's worthwhile tracking dependencies for
- // them individually.
- if static_count == 4 || changing_count == 4 {
- tile_mod = Some(TileModification::Merge);
- }
- }
- }
- }
-
- match tile_mod {
- Some(TileModification::Split) => {
- // To split a node, take the current dependency index buffer for this node, and
- // split it into child index buffers.
- let curr_indices = match self.kind {
- TileNodeKind::Node { .. } => {
- unreachable!("bug - only leaves can split");
- }
- TileNodeKind::Leaf { ref mut curr_indices, .. } => {
- curr_indices.take()
- }
- };
-
- let mut child_rects = [PictureBox2D::zero(); 4];
- TileNode::get_child_rects(&self.rect, &mut child_rects);
-
- let mut child_indices = [
- Vec::new(),
- Vec::new(),
- Vec::new(),
- Vec::new(),
- ];
-
- // Step through the index buffer, and add primitives to each of the children
- // that they intersect.
- for index in curr_indices {
- let prim = &curr_prims[index.0 as usize];
- for (child_rect, indices) in child_rects.iter().zip(child_indices.iter_mut()) {
- if prim.prim_clip_box.intersects(child_rect) {
- indices.push(index);
- }
- }
- }
-
- // Create the child nodes and switch from leaf -> node.
- let children = child_indices
- .iter_mut()
- .map(|i| TileNode::new_leaf(mem::replace(i, Vec::new())))
- .collect();
-
- self.kind = TileNodeKind::Node {
- children,
- };
- }
- Some(TileModification::Merge) => {
- // Construct a merged index buffer by collecting the dependency index buffers
- // from each child, and merging them into a de-duplicated index buffer.
- let merged_indices = match self.kind {
- TileNodeKind::Node { ref mut children, .. } => {
- let mut merged_indices = Vec::new();
-
- for child in children.iter() {
- let child_indices = match child.kind {
- TileNodeKind::Leaf { ref curr_indices, .. } => {
- curr_indices
- }
- TileNodeKind::Node { .. } => {
- unreachable!("bug: child is not a leaf");
- }
- };
- merged_indices.extend_from_slice(child_indices);
- }
-
- merged_indices.sort();
- merged_indices.dedup();
-
- merged_indices
- }
- TileNodeKind::Leaf { .. } => {
- unreachable!("bug - trying to merge a leaf");
- }
- };
-
- // Switch from a node to a leaf, with the combined index buffer
- self.kind = TileNodeKind::Leaf {
- prev_indices: Vec::new(),
- curr_indices: merged_indices,
- dirty_tracker: 0,
- frames_since_modified: 0,
- };
- }
- None => {
- // If this node didn't merge / split, then recurse into children
- // to see if they want to split / merge.
- if let TileNodeKind::Node { ref mut children, .. } = self.kind {
- for child in children.iter_mut() {
- child.maybe_merge_or_split(
- level+1,
- curr_prims,
- max_split_levels,
- );
- }
- }
- }
- }
- }
-
- /// Update the dirty state of this node, building the overall dirty rect
- fn update_dirty_rects(
- &mut self,
- prev_prims: &[PrimitiveDescriptor],
- curr_prims: &[PrimitiveDescriptor],
- prim_comparer: &mut PrimitiveComparer,
- dirty_rect: &mut PictureBox2D,
- compare_cache: &mut FastHashMap<PrimitiveComparisonKey, PrimitiveCompareResult>,
- invalidation_reason: &mut Option<InvalidationReason>,
- frame_context: &FrameVisibilityContext,
- ) {
- match self.kind {
- TileNodeKind::Node { ref mut children, .. } => {
- for child in children.iter_mut() {
- child.update_dirty_rects(
- prev_prims,
- curr_prims,
- prim_comparer,
- dirty_rect,
- compare_cache,
- invalidation_reason,
- frame_context,
- );
- }
- }
- TileNodeKind::Leaf { ref prev_indices, ref curr_indices, ref mut dirty_tracker, .. } => {
- // If the index buffers are of different length, they must be different
- if prev_indices.len() == curr_indices.len() {
- // Walk each index buffer, comparing primitives
- for (prev_index, curr_index) in prev_indices.iter().zip(curr_indices.iter()) {
- let i0 = prev_index.0 as usize;
- let i1 = curr_index.0 as usize;
-
- // Compare the primitives, caching the result in a hash map
- // to save comparisons in other tree nodes.
- let key = PrimitiveComparisonKey {
- prev_index: *prev_index,
- curr_index: *curr_index,
- };
-
- let prim_compare_result = *compare_cache
- .entry(key)
- .or_insert_with(|| {
- let prev = &prev_prims[i0];
- let curr = &curr_prims[i1];
- prim_comparer.compare_prim(prev, curr)
- });
-
- // If not the same, mark this node as dirty and update the dirty rect
- if prim_compare_result != PrimitiveCompareResult::Equal {
- if invalidation_reason.is_none() {
- *invalidation_reason = Some(InvalidationReason::Content);
- }
- *dirty_rect = self.rect.union(dirty_rect);
- *dirty_tracker = *dirty_tracker | 1;
- break;
- }
- }
- } else {
- if invalidation_reason.is_none() {
- *invalidation_reason = Some(InvalidationReason::PrimCount);
- }
- *dirty_rect = self.rect.union(dirty_rect);
- *dirty_tracker = *dirty_tracker | 1;
- }
- }
- }
- }
-}
-
impl CompositeState {
// A helper function to destroy all native surfaces for a given list of tiles
pub fn destroy_native_tiles<'a, I: Iterator<Item = &'a mut Box<Tile>>>(
