/* 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/. */ //! Internal representation of clips in WebRender. //! //! # Data structures //! //! There are a number of data structures involved in the clip module: //! //! - ClipStore - Main interface used by other modules. //! //! - ClipItem - A single clip item (e.g. a rounded rect, or a box shadow). //! These are an exposed API type, stored inline in a ClipNode. //! //! - ClipNode - A ClipItem with an attached GPU handle. The GPU handle is populated //! when a ClipNodeInstance is built from this node (which happens while //! preparing primitives for render). //! //! ClipNodeInstance - A ClipNode with attached positioning information (a spatial //! node index). This is stored as a contiguous array of nodes //! within the ClipStore. //! //! ```ascii //! +-----------------------+-----------------------+-----------------------+ //! | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | //! +-----------------------+-----------------------+-----------------------+ //! | ClipItem | ClipItem | ClipItem | //! | Spatial Node Index | Spatial Node Index | Spatial Node Index | //! | GPU cache handle | GPU cache handle | GPU cache handle | //! | ... | ... | ... | //! +-----------------------+-----------------------+-----------------------+ //! 0 1 2 //! +----------------+ | | //! | ClipNodeRange |____| | //! | index: 1 | | //! | count: 2 |___________________________________________________| //! +----------------+ //! ``` //! //! - ClipNodeRange - A clip item range identifies a range of clip nodes instances. //! It is stored as an (index, count). //! //! - ClipChainNode - A clip chain node contains a handle to an interned clip item, //! positioning information (from where the clip was defined), and //! an optional parent link to another ClipChainNode. ClipChainId //! is an index into an array, or ClipChainId::NONE for no parent. //! //! ```ascii //! +----------------+ ____+----------------+ ____+----------------+ /---> ClipChainId::NONE //! | ClipChainNode | | | ClipChainNode | | | ClipChainNode | | //! +----------------+ | +----------------+ | +----------------+ | //! | ClipDataHandle | | | ClipDataHandle | | | ClipDataHandle | | //! | Spatial index | | | Spatial index | | | Spatial index | | //! | Parent Id |___| | Parent Id |___| | Parent Id |___| //! | ... | | ... | | ... | //! +----------------+ +----------------+ +----------------+ //! ``` //! //! - ClipChainInstance - A ClipChain that has been built for a specific primitive + positioning node. //! //! When given a clip chain ID, and a local primitive rect and its spatial node, the clip module //! creates a clip chain instance. This is a struct with various pieces of useful information //! (such as a local clip rect). It also contains a (index, count) //! range specifier into an index buffer of the ClipNodeInstance structures that are actually relevant //! for this clip chain instance. The index buffer structure allows a single array to be used for //! all of the clip-chain instances built in a single frame. Each entry in the index buffer //! also stores some flags relevant to the clip node in this positioning context. //! //! ```ascii //! +----------------------+ //! | ClipChainInstance | //! +----------------------+ //! | ... | //! | local_clip_rect |________________________________________________________________________ //! | clips_range |_______________ | //! +----------------------+ | | //! | | //! +------------------+------------------+------------------+------------------+------------------+ //! | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | ClipNodeInstance | //! +------------------+------------------+------------------+------------------+------------------+ //! | flags | flags | flags | flags | flags | //! | ... | ... | ... | ... | ... | //! +------------------+------------------+------------------+------------------+------------------+ //! ``` //! //! # Rendering clipped primitives //! //! See the [`segment` module documentation][segment.rs]. //! //! //! [segment.rs]: ../segment/index.html //! use api::{BorderRadius, ClipMode, ComplexClipRegion, ImageMask, ClipId, ClipChainId}; use api::{BoxShadowClipMode, FillRule, ImageKey, ImageRendering}; use api::units::*; use crate::image_tiling::{self, Repetition}; use crate::border::{ensure_no_corner_overlap, BorderRadiusAu}; use crate::box_shadow::{BLUR_SAMPLE_SCALE, BoxShadowClipSource, BoxShadowCacheKey}; use crate::spatial_tree::{SpatialTree, SpatialNodeIndex}; use crate::ellipse::Ellipse; use crate::gpu_cache::GpuCache; use crate::gpu_types::{BoxShadowStretchMode}; use crate::intern; use crate::internal_types::{FastHashMap, FastHashSet, LayoutPrimitiveInfo}; use crate::prim_store::{VisibleMaskImageTile}; use crate::prim_store::{PointKey, SizeKey, RectangleKey, PolygonKey}; use crate::render_task_cache::to_cache_size; use crate::resource_cache::{ImageRequest, ResourceCache}; use crate::scene_builder_thread::Interners; use crate::space::SpaceMapper; use crate::util::{clamp_to_scale_factor, MaxRect, extract_inner_rect_safe, project_rect, ScaleOffset}; use euclid::approxeq::ApproxEq; use std::{iter, ops, u32, mem}; /// A (non-leaf) node inside a clip-tree #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] #[derive(MallocSizeOf)] pub struct ClipTreeNode { pub handle: ClipDataHandle, pub parent: ClipNodeId, children: Vec, // TODO(gw): Consider adding a default leaf for cases when the local_clip_rect is not relevant, // that can be shared among primitives (to reduce amount of clip-chain building). } /// A leaf node in a clip-tree. Any primitive that is clipped will have a handle to /// a clip-tree leaf. #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] #[derive(MallocSizeOf)] pub struct ClipTreeLeaf { pub node_id: ClipNodeId, // TODO(gw): For now, this preserves the ability to build a culling rect // from the supplied leaf local clip rect on the primitive. In // future, we'll expand this to be more efficient by combining // it will compatible clip rects from the `node_id`. pub local_clip_rect: LayoutRect, } /// ID for a ClipTreeNode #[derive(Debug, Copy, Clone, PartialEq, MallocSizeOf, Eq, Hash)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipNodeId(u32); impl ClipNodeId { pub const NONE: ClipNodeId = ClipNodeId(0); } /// ID for a ClipTreeLeaf #[derive(Debug, Copy, Clone, PartialEq, MallocSizeOf, Eq, Hash)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipLeafId(u32); /// A clip-tree built during scene building and used during frame-building to apply clips to primitives. #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipTree { nodes: Vec, leaves: Vec, clip_root_stack: Vec, } impl ClipTree { pub fn new() -> Self { ClipTree { nodes: vec![ ClipTreeNode { handle: ClipDataHandle::INVALID, children: Vec::new(), parent: ClipNodeId::NONE, } ], leaves: Vec::new(), clip_root_stack: vec![ ClipNodeId::NONE, ], } } /// Add a set of clips to the provided tree node id, reusing existing /// nodes in the tree where possible fn add_impl( id: ClipNodeId, clips: &[ClipDataHandle], nodes: &mut Vec, ) -> ClipNodeId { if clips.is_empty() { return id; } let handle = clips[0]; let next_clips = &clips[1..]; let node_index = nodes[id.0 as usize] .children .iter() .find(|n| nodes[n.0 as usize].handle == handle) .cloned(); let node_index = match node_index { Some(node_index) => node_index, None => { let node_index = ClipNodeId(nodes.len() as u32); nodes[id.0 as usize].children.push(node_index); let node = ClipTreeNode { handle, children: Vec::new(), parent: id, }; nodes.push(node); node_index } }; ClipTree::add_impl( node_index, next_clips, nodes, ) } /// Add a set of clips to the provided tree node id, reusing existing /// nodes in the tree where possible pub fn add( &mut self, root: ClipNodeId, clips: &[ClipDataHandle], ) -> ClipNodeId { ClipTree::add_impl( root, clips, &mut self.nodes, ) } /// Get the current clip root (the node in the clip-tree where clips can be /// ignored when building the clip-chain instance for a primitive) pub fn current_clip_root(&self) -> ClipNodeId { self.clip_root_stack.last().cloned().unwrap() } /// Push a clip root (e.g. when a surface is encountered) that prevents clips /// from this node and above being applied to primitives within the root. pub fn push_clip_root_leaf(&mut self, clip_leaf_id: ClipLeafId) { let leaf = &self.leaves[clip_leaf_id.0 as usize]; self.clip_root_stack.push(leaf.node_id); } /// Push a clip root (e.g. when a surface is encountered) that prevents clips /// from this node and above being applied to primitives within the root. pub fn push_clip_root_node(&mut self, clip_node_id: ClipNodeId) { self.clip_root_stack.push(clip_node_id); } /// Pop a clip root, when exiting a surface. pub fn pop_clip_root(&mut self) { self.clip_root_stack.pop().unwrap(); } /// Retrieve a clip tree node by id pub fn get_node(&self, id: ClipNodeId) -> &ClipTreeNode { assert!(id != ClipNodeId::NONE); &self.nodes[id.0 as usize] } /// Retrieve a clip tree leaf by id pub fn get_leaf(&self, id: ClipLeafId) -> &ClipTreeLeaf { &self.leaves[id.0 as usize] } /// Debug print the clip-tree #[allow(unused)] pub fn print(&self) { use crate::print_tree::PrintTree; fn print_node( id: ClipNodeId, nodes: &[ClipTreeNode], pt: &mut T, ) { let node = &nodes[id.0 as usize]; pt.new_level(format!("{:?}", id)); pt.add_item(format!("{:?}", node.handle)); for child_id in &node.children { print_node(*child_id, nodes, pt); } pt.end_level(); } fn print_leaf( id: ClipLeafId, leaves: &[ClipTreeLeaf], pt: &mut T, ) { let leaf = &leaves[id.0 as usize]; pt.new_level(format!("{:?}", id)); pt.add_item(format!("node_id: {:?}", leaf.node_id)); pt.add_item(format!("local_clip_rect: {:?}", leaf.local_clip_rect)); pt.end_level(); } let mut pt = PrintTree::new("clip tree"); print_node(ClipNodeId::NONE, &self.nodes, &mut pt); for i in 0 .. self.leaves.len() { print_leaf(ClipLeafId(i as u32), &self.leaves, &mut pt); } } /// Find the lowest common ancestor of two clip tree nodes. This is useful /// to identify shared clips between primitives attached to different clip-leaves. pub fn find_lowest_common_ancestor( &self, mut node1: ClipNodeId, mut node2: ClipNodeId, ) -> ClipNodeId { // TODO(gw): Consider caching / storing the depth in the node? fn get_node_depth( id: ClipNodeId, nodes: &[ClipTreeNode], ) -> usize { let mut depth = 0; let mut current = id; while current != ClipNodeId::NONE { let node = &nodes[current.0 as usize]; depth += 1; current = node.parent; } depth } let mut depth1 = get_node_depth(node1, &self.nodes); let mut depth2 = get_node_depth(node2, &self.nodes); while depth1 > depth2 { node1 = self.nodes[node1.0 as usize].parent; depth1 -= 1; } while depth2 > depth1 { node2 = self.nodes[node2.0 as usize].parent; depth2 -= 1; } while node1 != node2 { node1 = self.nodes[node1.0 as usize].parent; node2 = self.nodes[node2.0 as usize].parent; } node1 } } /// Represents a clip-chain as defined by the public API that we decompose in to /// the clip-tree. In future, we would like to remove this and have Gecko directly /// build the clip-tree. #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipChain { parent: Option, clips: Vec, } #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipStackEntry { /// Cache the previous clip-chain build, since this is a common case last_clip_chain_cache: Option<(ClipChainId, ClipNodeId)>, /// Set of clips that were already seen and included in clip_node_id seen_clips: FastHashSet, /// The build clip_node_id for this level of the stack clip_node_id: ClipNodeId, } /// Used by the scene builder to build the clip-tree that is part of the built scene. #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipTreeBuilder { /// Clips defined by the display list clip_map: FastHashMap, /// Clip-chains defined by the display list clip_chains: Vec, clip_chain_map: FastHashMap, /// List of clips pushed/popped by grouping items, such as stacking contexts and iframes clip_stack: Vec, /// The tree we are building tree: ClipTree, /// A temporary buffer stored here to avoid constant heap allocs/frees clip_handles_buffer: Vec, } impl ClipTreeBuilder { pub fn new() -> Self { ClipTreeBuilder { clip_map: FastHashMap::default(), clip_chain_map: FastHashMap::default(), clip_chains: Vec::new(), clip_stack: vec![ ClipStackEntry { clip_node_id: ClipNodeId::NONE, last_clip_chain_cache: None, seen_clips: FastHashSet::default(), }, ], tree: ClipTree::new(), clip_handles_buffer: Vec::new(), } } /// Define a new rect clip pub fn define_rect_clip( &mut self, id: ClipId, handle: ClipDataHandle, ) { self.clip_map.insert(id, handle); } /// Define a new rounded rect clip pub fn define_rounded_rect_clip( &mut self, id: ClipId, handle: ClipDataHandle, ) { self.clip_map.insert(id, handle); } /// Define a image mask clip pub fn define_image_mask_clip( &mut self, id: ClipId, handle: ClipDataHandle, ) { self.clip_map.insert(id, handle); } /// Define a clip-chain pub fn define_clip_chain>( &mut self, id: ClipChainId, parent: Option, clips: I, ) { let parent = parent.map(|ref id| self.clip_chain_map[id]); let index = self.clip_chains.len(); let clips = clips.map(|clip_id| { self.clip_map[&clip_id] }).collect(); self.clip_chains.push(ClipChain { parent, clips, }); self.clip_chain_map.insert(id, index); } /// Push a clip-chain that will be applied to any prims built prior to next pop pub fn push_clip_chain( &mut self, clip_chain_id: Option, reset_seen: bool, ) { let (mut clip_node_id, mut seen_clips) = { let prev = self.clip_stack.last().unwrap(); (prev.clip_node_id, prev.seen_clips.clone()) }; if let Some(clip_chain_id) = clip_chain_id { if clip_chain_id != ClipChainId::INVALID { self.clip_handles_buffer.clear(); let clip_chain_index = self.clip_chain_map[&clip_chain_id]; ClipTreeBuilder::add_clips( clip_chain_index, &mut seen_clips, &mut self.clip_handles_buffer, &self.clip_chains, ); clip_node_id = self.tree.add( clip_node_id, &self.clip_handles_buffer, ); } } if reset_seen { seen_clips.clear(); } self.clip_stack.push(ClipStackEntry { last_clip_chain_cache: None, clip_node_id, seen_clips, }); } /// Push a clip-id that will be applied to any prims built prior to next pop pub fn push_clip_id( &mut self, clip_id: ClipId, ) { let (clip_node_id, mut seen_clips) = { let prev = self.clip_stack.last().unwrap(); (prev.clip_node_id, prev.seen_clips.clone()) }; self.clip_handles_buffer.clear(); let clip_index = self.clip_map[&clip_id]; if seen_clips.insert(clip_index) { self.clip_handles_buffer.push(clip_index); } let clip_node_id = self.tree.add( clip_node_id, &self.clip_handles_buffer, ); self.clip_stack.push(ClipStackEntry { last_clip_chain_cache: None, seen_clips, clip_node_id, }); } /// Pop a clip off the clip_stack, when exiting a grouping item pub fn pop_clip(&mut self) { self.clip_stack.pop().unwrap(); } /// Add clips from a given clip-chain to the set of clips for a primitive during clip-set building fn add_clips( clip_chain_index: usize, seen_clips: &mut FastHashSet, output: &mut Vec, clip_chains: &[ClipChain], ) { // TODO(gw): It's possible that we may see clip outputs that include identical clips // (e.g. if there is a clip positioned by two spatial nodes, where one spatial // node is a child of the other, and has an identity transform). If we ever // see this in real-world cases, it might be worth checking for that here and // excluding them, to ensure the shape of the tree matches what we need for // finding shared_clips for tile caches etc. let clip_chain = &clip_chains[clip_chain_index]; if let Some(parent) = clip_chain.parent { ClipTreeBuilder::add_clips( parent, seen_clips, output, clip_chains, ); } for clip_index in clip_chain.clips.iter().rev() { if seen_clips.insert(*clip_index) { output.push(*clip_index); } } } /// Main entry point to build a path in the clip-tree for a given primitive pub fn build_clip_set( &mut self, clip_chain_id: ClipChainId, ) -> ClipNodeId { let clip_stack = self.clip_stack.last_mut().unwrap(); if clip_chain_id == ClipChainId::INVALID { clip_stack.clip_node_id } else { if let Some((cached_clip_chain, cached_clip_node)) = clip_stack.last_clip_chain_cache { if cached_clip_chain == clip_chain_id { return cached_clip_node; } } let clip_chain_index = self.clip_chain_map[&clip_chain_id]; self.clip_handles_buffer.clear(); ClipTreeBuilder::add_clips( clip_chain_index, &mut clip_stack.seen_clips, &mut self.clip_handles_buffer, &self.clip_chains, ); // We mutated the `clip_stack.seen_clips` in order to remove duplicate clips from // the supplied `clip_chain_id`. Now step through and remove any clips we added // to the set, so we don't get incorrect results next time `build_clip_set` is // called for a different clip-chain. Doing it this way rather than cloning means // we avoid heap allocations for each `build_clip_set` call. for handle in &self.clip_handles_buffer { clip_stack.seen_clips.remove(handle); } let clip_node_id = self.tree.add( clip_stack.clip_node_id, &self.clip_handles_buffer, ); clip_stack.last_clip_chain_cache = Some((clip_chain_id, clip_node_id)); clip_node_id } } /// Recursive impl to check if a clip-chain has complex (non-rectangular) clips fn has_complex_clips_impl( &self, clip_chain_index: usize, interners: &Interners, ) -> bool { let clip_chain = &self.clip_chains[clip_chain_index]; for clip_handle in &clip_chain.clips { let clip_info = &interners.clip[*clip_handle]; if let ClipNodeKind::Complex = clip_info.key.kind.node_kind() { return true; } } match clip_chain.parent { Some(parent) => self.has_complex_clips_impl(parent, interners), None => false, } } /// Check if a clip-chain has complex (non-rectangular) clips pub fn clip_chain_has_complex_clips( &self, clip_chain_id: ClipChainId, interners: &Interners, ) -> bool { let clip_chain_index = self.clip_chain_map[&clip_chain_id]; self.has_complex_clips_impl(clip_chain_index, interners) } /// Check if a clip-node has complex (non-rectangular) clips pub fn clip_node_has_complex_clips( &self, clip_node_id: ClipNodeId, interners: &Interners, ) -> bool { let mut current = clip_node_id; while current != ClipNodeId::NONE { let node = &self.tree.nodes[current.0 as usize]; let clip_info = &interners.clip[node.handle]; if let ClipNodeKind::Complex = clip_info.key.kind.node_kind() { return true; } current = node.parent; } false } /// Finalize building and return the clip-tree pub fn finalize(self) -> ClipTree { self.tree } /// Get a clip node by id pub fn get_node(&self, id: ClipNodeId) -> &ClipTreeNode { assert!(id != ClipNodeId::NONE); &self.tree.nodes[id.0 as usize] } /// Get a clip leaf by id pub fn get_leaf(&self, id: ClipLeafId) -> &ClipTreeLeaf { &self.tree.leaves[id.0 as usize] } /// Build a clip-leaf for a tile-cache pub fn build_for_tile_cache( &mut self, clip_node_id: ClipNodeId, extra_clips: &[ClipId], ) -> ClipLeafId { self.clip_handles_buffer.clear(); for clip_id in extra_clips { let handle = self.clip_map[clip_id]; self.clip_handles_buffer.push(handle); } let node_id = self.tree.add( clip_node_id, &self.clip_handles_buffer, ); let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32); self.tree.leaves.push(ClipTreeLeaf { node_id, local_clip_rect: LayoutRect::max_rect(), }); clip_leaf_id } /// Build a clip-leaf for a picture pub fn build_for_picture( &mut self, clip_node_id: ClipNodeId, ) -> ClipLeafId { let node_id = self.tree.add( clip_node_id, &[], ); let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32); self.tree.leaves.push(ClipTreeLeaf { node_id, local_clip_rect: LayoutRect::max_rect(), }); clip_leaf_id } /// Build a clip-leaf for a normal primitive pub fn build_for_prim( &mut self, clip_node_id: ClipNodeId, info: &LayoutPrimitiveInfo, extra_clips: &[ClipItemKey], interners: &mut Interners, ) -> ClipLeafId { let node_id = if extra_clips.is_empty() { clip_node_id } else { // TODO(gw): Cache the previous build of clip-node / clip-leaf to handle cases where we get a // lot of primitives referencing the same clip set (e.g. dl_mutate and similar tests) self.clip_handles_buffer.clear(); for item in extra_clips { // Intern this clip item, and store the handle // in the clip chain node. let handle = interners.clip.intern(item, || { ClipInternData { key: item.clone(), } }); self.clip_handles_buffer.push(handle); } self.tree.add( clip_node_id, &self.clip_handles_buffer, ) }; let clip_leaf_id = ClipLeafId(self.tree.leaves.len() as u32); self.tree.leaves.push(ClipTreeLeaf { node_id, local_clip_rect: info.clip_rect, }); clip_leaf_id } // Find the LCA for two given clip nodes pub fn find_lowest_common_ancestor( &self, node1: ClipNodeId, node2: ClipNodeId, ) -> ClipNodeId { self.tree.find_lowest_common_ancestor(node1, node2) } } // Type definitions for interning clip nodes. #[derive(Copy, Clone, Debug, MallocSizeOf, PartialEq, Eq, Hash)] #[cfg_attr(any(feature = "serde"), derive(Deserialize, Serialize))] pub enum ClipIntern {} pub type ClipDataStore = intern::DataStore; pub type ClipDataHandle = intern::Handle; /// Helper to identify simple clips (normal rects) from other kinds of clips, /// which can often be handled via fast code paths. #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] #[derive(Debug, Copy, Clone, MallocSizeOf)] pub enum ClipNodeKind { /// A normal clip rectangle, with Clip mode. Rectangle, /// A rectangle with ClipOut, or any other kind of clip. Complex, } // Result of comparing a clip node instance against a local rect. #[derive(Debug)] enum ClipResult { // The clip does not affect the region at all. Accept, // The clip prevents the region from being drawn. Reject, // The clip affects part of the region. This may // require a clip mask, depending on other factors. Partial, } // A clip node is a single clip source, along with some // positioning information and implementation details // that control where the GPU data for this clip source // can be found. #[derive(Debug)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] #[derive(MallocSizeOf)] pub struct ClipNode { pub item: ClipItem, } // Convert from an interning key for a clip item // to a clip node, which is cached in the document. impl From for ClipNode { fn from(item: ClipItemKey) -> Self { let kind = match item.kind { ClipItemKeyKind::Rectangle(rect, mode) => { ClipItemKind::Rectangle { rect: rect.into(), mode } } ClipItemKeyKind::RoundedRectangle(rect, radius, mode) => { ClipItemKind::RoundedRectangle { rect: rect.into(), radius: radius.into(), mode, } } ClipItemKeyKind::ImageMask(rect, image, polygon_handle) => { ClipItemKind::Image { image, rect: rect.into(), polygon_handle, } } ClipItemKeyKind::BoxShadow(shadow_rect_fract_offset, shadow_rect_size, shadow_radius, prim_shadow_rect, blur_radius, clip_mode) => { ClipItemKind::new_box_shadow( shadow_rect_fract_offset.into(), shadow_rect_size.into(), shadow_radius.into(), prim_shadow_rect.into(), blur_radius.to_f32_px(), clip_mode, ) } }; ClipNode { item: ClipItem { kind, spatial_node_index: item.spatial_node_index, }, } } } // Flags that are attached to instances of clip nodes. bitflags! { #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] #[derive(MallocSizeOf)] pub struct ClipNodeFlags: u8 { const SAME_SPATIAL_NODE = 0x1; const SAME_COORD_SYSTEM = 0x2; const USE_FAST_PATH = 0x4; } } // When a clip node is found to be valid for a // clip chain instance, it's stored in an index // buffer style structure. This struct contains // an index to the node data itself, as well as // some flags describing how this clip node instance // is positioned. #[derive(Debug, MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipNodeInstance { pub handle: ClipDataHandle, pub flags: ClipNodeFlags, pub visible_tiles: Option>, } impl ClipNodeInstance { pub fn has_visible_tiles(&self) -> bool { self.visible_tiles.is_some() } } // A range of clip node instances that were found by // building a clip chain instance. #[derive(Debug, Copy, Clone)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipNodeRange { pub first: u32, pub count: u32, } impl ClipNodeRange { pub fn to_range(&self) -> ops::Range { let start = self.first as usize; let end = start + self.count as usize; ops::Range { start, end, } } } /// A helper struct for converting between coordinate systems /// of clip sources and primitives. // todo(gw): optimize: // separate arrays for matrices // cache and only build as needed. //TODO: merge with `CoordinateSpaceMapping`? #[derive(Debug, MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] enum ClipSpaceConversion { Local, ScaleOffset(ScaleOffset), Transform(LayoutToWorldTransform), } impl ClipSpaceConversion { /// Construct a new clip space converter between two spatial nodes. fn new( prim_spatial_node_index: SpatialNodeIndex, clip_spatial_node_index: SpatialNodeIndex, spatial_tree: &SpatialTree, ) -> Self { //Note: this code is different from `get_relative_transform` in a way that we only try // getting the relative transform if it's Local or ScaleOffset, // falling back to the world transform otherwise. let clip_spatial_node = spatial_tree.get_spatial_node(clip_spatial_node_index); let prim_spatial_node = spatial_tree.get_spatial_node(prim_spatial_node_index); if prim_spatial_node_index == clip_spatial_node_index { ClipSpaceConversion::Local } else if prim_spatial_node.coordinate_system_id == clip_spatial_node.coordinate_system_id { let scale_offset = prim_spatial_node.content_transform .inverse() .accumulate(&clip_spatial_node.content_transform); ClipSpaceConversion::ScaleOffset(scale_offset) } else { ClipSpaceConversion::Transform( spatial_tree .get_world_transform(clip_spatial_node_index) .into_transform() ) } } fn to_flags(&self) -> ClipNodeFlags { match *self { ClipSpaceConversion::Local => { ClipNodeFlags::SAME_SPATIAL_NODE | ClipNodeFlags::SAME_COORD_SYSTEM } ClipSpaceConversion::ScaleOffset(..) => { ClipNodeFlags::SAME_COORD_SYSTEM } ClipSpaceConversion::Transform(..) => { ClipNodeFlags::empty() } } } } // Temporary information that is cached and reused // during building of a clip chain instance. #[derive(MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] struct ClipNodeInfo { conversion: ClipSpaceConversion, handle: ClipDataHandle, } impl ClipNodeInfo { fn create_instance( &self, node: &ClipNode, clipped_rect: &LayoutRect, gpu_cache: &mut GpuCache, resource_cache: &mut ResourceCache, mask_tiles: &mut Vec, spatial_tree: &SpatialTree, request_resources: bool, ) -> Option { // Calculate some flags that are required for the segment // building logic. let mut flags = self.conversion.to_flags(); // Some clip shaders support a fast path mode for simple clips. // TODO(gw): We could also apply fast path when segments are created, since we only write // the mask for a single corner at a time then, so can always consider radii uniform. let is_raster_2d = flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM) || spatial_tree .get_world_viewport_transform(node.item.spatial_node_index) .is_2d_axis_aligned(); if is_raster_2d && node.item.kind.supports_fast_path_rendering() { flags |= ClipNodeFlags::USE_FAST_PATH; } let mut visible_tiles = None; if let ClipItemKind::Image { rect, image, .. } = node.item.kind { let request = ImageRequest { key: image, rendering: ImageRendering::Auto, tile: None, }; if let Some(props) = resource_cache.get_image_properties(image) { if let Some(tile_size) = props.tiling { let tile_range_start = mask_tiles.len(); // Bug 1648323 - It is unclear why on rare occasions we get // a clipped_rect that does not intersect the clip's mask rect. // defaulting to clipped_rect here results in zero repetitions // which clips the primitive entirely. let visible_rect = clipped_rect.intersection(&rect).unwrap_or(*clipped_rect); let repetitions = image_tiling::repetitions( &rect, &visible_rect, rect.size(), ); for Repetition { origin, .. } in repetitions { let layout_image_rect = LayoutRect::from_origin_and_size( origin, rect.size(), ); let tiles = image_tiling::tiles( &layout_image_rect, &visible_rect, &props.visible_rect, tile_size as i32, ); for tile in tiles { if request_resources { resource_cache.request_image( request.with_tile(tile.offset), gpu_cache, ); } mask_tiles.push(VisibleMaskImageTile { tile_offset: tile.offset, tile_rect: tile.rect, }); } } visible_tiles = Some(tile_range_start..mask_tiles.len()); } else if request_resources { resource_cache.request_image(request, gpu_cache); } } else { // If the supplied image key doesn't exist in the resource cache, // skip the clip node since there is nothing to mask with. warn!("Clip mask with missing image key {:?}", request.key); return None; } } Some(ClipNodeInstance { handle: self.handle, flags, visible_tiles, }) } } impl ClipNode { pub fn update( &mut self, device_pixel_scale: DevicePixelScale, ) { match self.item.kind { ClipItemKind::Image { .. } | ClipItemKind::Rectangle { .. } | ClipItemKind::RoundedRectangle { .. } => {} ClipItemKind::BoxShadow { ref mut source } => { // Quote from https://drafts.csswg.org/css-backgrounds-3/#shadow-blur // "the image that would be generated by applying to the shadow a // Gaussian blur with a standard deviation equal to half the blur radius." let blur_radius_dp = source.blur_radius * 0.5; // Create scaling from requested size to cache size. let mut content_scale = LayoutToWorldScale::new(1.0) * device_pixel_scale; content_scale.0 = clamp_to_scale_factor(content_scale.0, false); // Create the cache key for this box-shadow render task. let cache_size = to_cache_size(source.shadow_rect_alloc_size, &mut content_scale); let bs_cache_key = BoxShadowCacheKey { blur_radius_dp: (blur_radius_dp * content_scale.0).round() as i32, clip_mode: source.clip_mode, original_alloc_size: (source.original_alloc_size * content_scale).round().to_i32(), br_top_left: (source.shadow_radius.top_left * content_scale).round().to_i32(), br_top_right: (source.shadow_radius.top_right * content_scale).round().to_i32(), br_bottom_right: (source.shadow_radius.bottom_right * content_scale).round().to_i32(), br_bottom_left: (source.shadow_radius.bottom_left * content_scale).round().to_i32(), device_pixel_scale: Au::from_f32_px(content_scale.0), }; source.cache_key = Some((cache_size, bs_cache_key)); } } } } #[derive(Default)] pub struct ClipStoreScratchBuffer { clip_node_instances: Vec, mask_tiles: Vec, } /// The main clipping public interface that other modules access. #[derive(MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] pub struct ClipStore { pub clip_node_instances: Vec, mask_tiles: Vec, active_clip_node_info: Vec, active_local_clip_rect: Option, active_pic_coverage_rect: PictureRect, } // A clip chain instance is what gets built for a given clip // chain id + local primitive region + positioning node. #[derive(Debug)] #[cfg_attr(feature = "capture", derive(Serialize))] pub struct ClipChainInstance { pub clips_range: ClipNodeRange, // Combined clip rect for clips that are in the // same coordinate system as the primitive. pub local_clip_rect: LayoutRect, pub has_non_local_clips: bool, // If true, this clip chain requires allocation // of a clip mask. pub needs_mask: bool, // Combined clip rect in picture space (may // be more conservative that local_clip_rect). pub pic_coverage_rect: PictureRect, // Space, in which the `pic_coverage_rect` is defined. pub pic_spatial_node_index: SpatialNodeIndex, } impl ClipChainInstance { pub fn empty() -> Self { ClipChainInstance { clips_range: ClipNodeRange { first: 0, count: 0, }, local_clip_rect: LayoutRect::zero(), has_non_local_clips: false, needs_mask: false, pic_coverage_rect: PictureRect::zero(), pic_spatial_node_index: SpatialNodeIndex::INVALID, } } } impl ClipStore { pub fn new() -> Self { ClipStore { clip_node_instances: Vec::new(), mask_tiles: Vec::new(), active_clip_node_info: Vec::new(), active_local_clip_rect: None, active_pic_coverage_rect: PictureRect::max_rect(), } } pub fn get_instance_from_range( &self, node_range: &ClipNodeRange, index: u32, ) -> &ClipNodeInstance { &self.clip_node_instances[(node_range.first + index) as usize] } /// Setup the active clip chains for building a clip chain instance. pub fn set_active_clips( &mut self, prim_spatial_node_index: SpatialNodeIndex, pic_spatial_node_index: SpatialNodeIndex, clip_leaf_id: ClipLeafId, spatial_tree: &SpatialTree, clip_data_store: &ClipDataStore, clip_tree: &ClipTree, ) { self.active_clip_node_info.clear(); self.active_local_clip_rect = None; self.active_pic_coverage_rect = PictureRect::max_rect(); let clip_root = clip_tree.current_clip_root(); let clip_leaf = clip_tree.get_leaf(clip_leaf_id); let mut local_clip_rect = clip_leaf.local_clip_rect; let mut current = clip_leaf.node_id; while current != clip_root { let node = clip_tree.get_node(current); if !add_clip_node_to_current_chain( node.handle, prim_spatial_node_index, pic_spatial_node_index, &mut local_clip_rect, &mut self.active_clip_node_info, &mut self.active_pic_coverage_rect, clip_data_store, spatial_tree, ) { return; } current = node.parent; } self.active_local_clip_rect = Some(local_clip_rect); } /// Setup the active clip chains, based on an existing primitive clip chain instance. pub fn set_active_clips_from_clip_chain( &mut self, prim_clip_chain: &ClipChainInstance, prim_spatial_node_index: SpatialNodeIndex, spatial_tree: &SpatialTree, clip_data_store: &ClipDataStore, ) { // TODO(gw): Although this does less work than set_active_clips(), it does // still do some unnecessary work (such as the clip space conversion). // We could consider optimizing this if it ever shows up in a profile. self.active_clip_node_info.clear(); self.active_local_clip_rect = Some(prim_clip_chain.local_clip_rect); self.active_pic_coverage_rect = prim_clip_chain.pic_coverage_rect; let clip_instances = &self .clip_node_instances[prim_clip_chain.clips_range.to_range()]; for clip_instance in clip_instances { let clip = &clip_data_store[clip_instance.handle]; let conversion = ClipSpaceConversion::new( prim_spatial_node_index, clip.item.spatial_node_index, spatial_tree, ); self.active_clip_node_info.push(ClipNodeInfo { handle: clip_instance.handle, conversion, }); } } /// Given a clip-chain instance, return a safe rect within the visible region /// that can be assumed to be unaffected by clip radii. Returns None if it /// encounters any complex cases, just handling rounded rects in the same /// coordinate system as the clip-chain for now. pub fn get_inner_rect_for_clip_chain( &self, clip_chain: &ClipChainInstance, clip_data_store: &ClipDataStore, spatial_tree: &SpatialTree, ) -> Option { let mut inner_rect = clip_chain.pic_coverage_rect; let clip_instances = &self .clip_node_instances[clip_chain.clips_range.to_range()]; for clip_instance in clip_instances { // Don't handle mapping between coord systems for now if !clip_instance.flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM) { return None; } let clip_node = &clip_data_store[clip_instance.handle]; match clip_node.item.kind { // Ignore any clips which are complex or impossible to calculate // inner rects for now ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } | ClipItemKind::Image { .. } | ClipItemKind::BoxShadow { .. } | ClipItemKind::RoundedRectangle { mode: ClipMode::ClipOut, .. } => { return None; } // Normal Clip rects are already handled by the clip-chain pic_coverage_rect, // no need to do anything here ClipItemKind::Rectangle { mode: ClipMode::Clip, .. } => {} ClipItemKind::RoundedRectangle { mode: ClipMode::Clip, rect, radius } => { // Get an inner rect for the rounded-rect clip let local_inner_rect = match extract_inner_rect_safe(&rect, &radius) { Some(rect) => rect, None => return None, }; // Map it from local -> picture space let mapper = SpaceMapper::new_with_target( clip_chain.pic_spatial_node_index, clip_node.item.spatial_node_index, PictureRect::max_rect(), spatial_tree, ); // Accumulate in to the inner_rect, in case there are multiple rounded-rect clips if let Some(pic_inner_rect) = mapper.map(&local_inner_rect) { inner_rect = inner_rect.intersection(&pic_inner_rect).unwrap_or(PictureRect::zero()); } } } } Some(inner_rect) } /// The main interface external code uses. Given a local primitive, positioning /// information, and a clip chain id, build an optimized clip chain instance. pub fn build_clip_chain_instance( &mut self, local_prim_rect: LayoutRect, prim_to_pic_mapper: &SpaceMapper, pic_to_world_mapper: &SpaceMapper, spatial_tree: &SpatialTree, gpu_cache: &mut GpuCache, resource_cache: &mut ResourceCache, device_pixel_scale: DevicePixelScale, world_rect: &WorldRect, clip_data_store: &mut ClipDataStore, request_resources: bool, ) -> Option { let local_clip_rect = match self.active_local_clip_rect { Some(rect) => rect, None => return None, }; profile_scope!("build_clip_chain_instance"); let local_bounding_rect = local_prim_rect.intersection(&local_clip_rect)?; let mut pic_coverage_rect = prim_to_pic_mapper.map(&local_bounding_rect)?; let world_clip_rect = pic_to_world_mapper.map(&pic_coverage_rect)?; // Now, we've collected all the clip nodes that *potentially* affect this // primitive region, and reduced the size of the prim region as much as possible. // Run through the clip nodes, and see which ones affect this prim region. let first_clip_node_index = self.clip_node_instances.len() as u32; let mut has_non_local_clips = false; let mut needs_mask = false; // For each potential clip node for node_info in self.active_clip_node_info.drain(..) { let node = &mut clip_data_store[node_info.handle]; // See how this clip affects the prim region. let clip_result = match node_info.conversion { ClipSpaceConversion::Local => { node.item.kind.get_clip_result(&local_bounding_rect) } ClipSpaceConversion::ScaleOffset(ref scale_offset) => { has_non_local_clips = true; node.item.kind.get_clip_result(&scale_offset.unmap_rect(&local_bounding_rect)) } ClipSpaceConversion::Transform(ref transform) => { has_non_local_clips = true; node.item.kind.get_clip_result_complex( transform, &world_clip_rect, world_rect, ) } }; match clip_result { ClipResult::Accept => { // Doesn't affect the primitive at all, so skip adding to list } ClipResult::Reject => { // Completely clips the supplied prim rect return None; } ClipResult::Partial => { // Needs a mask -> add to clip node indices // TODO(gw): Ensure this only runs once on each node per frame? node.update(device_pixel_scale); // Create the clip node instance for this clip node if let Some(instance) = node_info.create_instance( node, &local_bounding_rect, gpu_cache, resource_cache, &mut self.mask_tiles, spatial_tree, request_resources, ) { // As a special case, a partial accept of a clip rect that is // in the same coordinate system as the primitive doesn't need // a clip mask. Instead, it can be handled by the primitive // vertex shader as part of the local clip rect. This is an // important optimization for reducing the number of clip // masks that are allocated on common pages. needs_mask |= match node.item.kind { ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } | ClipItemKind::RoundedRectangle { .. } | ClipItemKind::Image { .. } | ClipItemKind::BoxShadow { .. } => { true } ClipItemKind::Rectangle { mode: ClipMode::Clip, .. } => { !instance.flags.contains(ClipNodeFlags::SAME_COORD_SYSTEM) } }; // Store this in the index buffer for this clip chain instance. self.clip_node_instances.push(instance); } } } } // Get the range identifying the clip nodes in the index buffer. let clips_range = ClipNodeRange { first: first_clip_node_index, count: self.clip_node_instances.len() as u32 - first_clip_node_index, }; // If this clip chain needs a mask, reduce the size of the mask allocation // by any clips that were in the same space as the picture. This can result // in much smaller clip mask allocations in some cases. Note that the ordering // here is important - the reduction must occur *after* the clip item accept // reject checks above, so that we don't eliminate masks accidentally (since // we currently only support a local clip rect in the vertex shader). if needs_mask { pic_coverage_rect = pic_coverage_rect.intersection(&self.active_pic_coverage_rect)?; } // Return a valid clip chain instance Some(ClipChainInstance { clips_range, has_non_local_clips, local_clip_rect, pic_coverage_rect, pic_spatial_node_index: prim_to_pic_mapper.ref_spatial_node_index, needs_mask, }) } pub fn begin_frame(&mut self, scratch: &mut ClipStoreScratchBuffer) { mem::swap(&mut self.clip_node_instances, &mut scratch.clip_node_instances); mem::swap(&mut self.mask_tiles, &mut scratch.mask_tiles); self.clip_node_instances.clear(); self.mask_tiles.clear(); } pub fn end_frame(&mut self, scratch: &mut ClipStoreScratchBuffer) { mem::swap(&mut self.clip_node_instances, &mut scratch.clip_node_instances); mem::swap(&mut self.mask_tiles, &mut scratch.mask_tiles); } pub fn visible_mask_tiles(&self, instance: &ClipNodeInstance) -> &[VisibleMaskImageTile] { if let Some(range) = &instance.visible_tiles { &self.mask_tiles[range.clone()] } else { &[] } } } pub struct ComplexTranslateIter { source: I, offset: LayoutVector2D, } impl> Iterator for ComplexTranslateIter { type Item = ComplexClipRegion; fn next(&mut self) -> Option { self.source .next() .map(|mut complex| { complex.rect = complex.rect.translate(self.offset); complex }) } } // The ClipItemKey is a hashable representation of the contents // of a clip item. It is used during interning to de-duplicate // clip nodes between frames and display lists. This allows quick // comparison of clip node equality by handle, and also allows // the uploaded GPU cache handle to be retained between display lists. // TODO(gw): Maybe we should consider constructing these directly // in the DL builder? #[derive(Copy, Debug, Clone, Eq, MallocSizeOf, PartialEq, Hash)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub enum ClipItemKeyKind { Rectangle(RectangleKey, ClipMode), RoundedRectangle(RectangleKey, BorderRadiusAu, ClipMode), ImageMask(RectangleKey, ImageKey, Option), BoxShadow(PointKey, SizeKey, BorderRadiusAu, RectangleKey, Au, BoxShadowClipMode), } impl ClipItemKeyKind { pub fn rectangle(rect: LayoutRect, mode: ClipMode) -> Self { ClipItemKeyKind::Rectangle(rect.into(), mode) } pub fn rounded_rect(rect: LayoutRect, mut radii: BorderRadius, mode: ClipMode) -> Self { if radii.is_zero() { ClipItemKeyKind::rectangle(rect, mode) } else { ensure_no_corner_overlap(&mut radii, rect.size()); ClipItemKeyKind::RoundedRectangle( rect.into(), radii.into(), mode, ) } } pub fn image_mask(image_mask: &ImageMask, mask_rect: LayoutRect, polygon_handle: Option) -> Self { ClipItemKeyKind::ImageMask( mask_rect.into(), image_mask.image, polygon_handle, ) } pub fn box_shadow( shadow_rect: LayoutRect, shadow_radius: BorderRadius, prim_shadow_rect: LayoutRect, blur_radius: f32, clip_mode: BoxShadowClipMode, ) -> Self { // Get the fractional offsets required to match the // source rect with a minimal rect. let fract_offset = LayoutPoint::new( shadow_rect.min.x.fract().abs(), shadow_rect.min.y.fract().abs(), ); ClipItemKeyKind::BoxShadow( fract_offset.into(), shadow_rect.size().into(), shadow_radius.into(), prim_shadow_rect.into(), Au::from_f32_px(blur_radius), clip_mode, ) } pub fn node_kind(&self) -> ClipNodeKind { match *self { ClipItemKeyKind::Rectangle(_, ClipMode::Clip) => ClipNodeKind::Rectangle, ClipItemKeyKind::Rectangle(_, ClipMode::ClipOut) | ClipItemKeyKind::RoundedRectangle(..) | ClipItemKeyKind::ImageMask(..) | ClipItemKeyKind::BoxShadow(..) => ClipNodeKind::Complex, } } } #[derive(Debug, Copy, Clone, Eq, MallocSizeOf, PartialEq, Hash)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipItemKey { pub kind: ClipItemKeyKind, pub spatial_node_index: SpatialNodeIndex, } /// The data available about an interned clip node during scene building #[derive(Debug, MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipInternData { pub key: ClipItemKey, } impl intern::InternDebug for ClipItemKey {} impl intern::Internable for ClipIntern { type Key = ClipItemKey; type StoreData = ClipNode; type InternData = ClipInternData; const PROFILE_COUNTER: usize = crate::profiler::INTERNED_CLIPS; } #[derive(Debug, MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub enum ClipItemKind { Rectangle { rect: LayoutRect, mode: ClipMode, }, RoundedRectangle { rect: LayoutRect, radius: BorderRadius, mode: ClipMode, }, Image { image: ImageKey, rect: LayoutRect, polygon_handle: Option, }, BoxShadow { source: BoxShadowClipSource, }, } #[derive(Debug, MallocSizeOf)] #[cfg_attr(feature = "capture", derive(Serialize))] #[cfg_attr(feature = "replay", derive(Deserialize))] pub struct ClipItem { pub kind: ClipItemKind, pub spatial_node_index: SpatialNodeIndex, } fn compute_box_shadow_parameters( shadow_rect_fract_offset: LayoutPoint, shadow_rect_size: LayoutSize, mut shadow_radius: BorderRadius, prim_shadow_rect: LayoutRect, blur_radius: f32, clip_mode: BoxShadowClipMode, ) -> BoxShadowClipSource { // Make sure corners don't overlap. ensure_no_corner_overlap(&mut shadow_radius, shadow_rect_size); let fract_size = LayoutSize::new( shadow_rect_size.width.fract().abs(), shadow_rect_size.height.fract().abs(), ); // Create a minimal size primitive mask to blur. In this // case, we ensure the size of each corner is the same, // to simplify the shader logic that stretches the blurred // result across the primitive. let max_corner_width = shadow_radius.top_left.width .max(shadow_radius.bottom_left.width) .max(shadow_radius.top_right.width) .max(shadow_radius.bottom_right.width); let max_corner_height = shadow_radius.top_left.height .max(shadow_radius.bottom_left.height) .max(shadow_radius.top_right.height) .max(shadow_radius.bottom_right.height); // Get maximum distance that can be affected by given blur radius. let blur_region = (BLUR_SAMPLE_SCALE * blur_radius).ceil(); // If the largest corner is smaller than the blur radius, we need to ensure // that it's big enough that the corners don't affect the middle segments. let used_corner_width = max_corner_width.max(blur_region); let used_corner_height = max_corner_height.max(blur_region); // Minimal nine-patch size, corner + internal + corner. let min_shadow_rect_size = LayoutSize::new( 2.0 * used_corner_width + blur_region, 2.0 * used_corner_height + blur_region, ); // The minimal rect to blur. let mut minimal_shadow_rect = LayoutRect::from_origin_and_size( LayoutPoint::new( blur_region + shadow_rect_fract_offset.x, blur_region + shadow_rect_fract_offset.y, ), LayoutSize::new( min_shadow_rect_size.width + fract_size.width, min_shadow_rect_size.height + fract_size.height, ), ); // If the width or height ends up being bigger than the original // primitive shadow rect, just blur the entire rect along that // axis and draw that as a simple blit. This is necessary for // correctness, since the blur of one corner may affect the blur // in another corner. let mut stretch_mode_x = BoxShadowStretchMode::Stretch; if shadow_rect_size.width < minimal_shadow_rect.width() { minimal_shadow_rect.max.x = minimal_shadow_rect.min.x + shadow_rect_size.width; stretch_mode_x = BoxShadowStretchMode::Simple; } let mut stretch_mode_y = BoxShadowStretchMode::Stretch; if shadow_rect_size.height < minimal_shadow_rect.height() { minimal_shadow_rect.max.y = minimal_shadow_rect.min.y + shadow_rect_size.height; stretch_mode_y = BoxShadowStretchMode::Simple; } // Expand the shadow rect by enough room for the blur to take effect. let shadow_rect_alloc_size = LayoutSize::new( 2.0 * blur_region + minimal_shadow_rect.width().ceil(), 2.0 * blur_region + minimal_shadow_rect.height().ceil(), ); BoxShadowClipSource { original_alloc_size: shadow_rect_alloc_size, shadow_rect_alloc_size, shadow_radius, prim_shadow_rect, blur_radius, clip_mode, stretch_mode_x, stretch_mode_y, render_task: None, cache_key: None, minimal_shadow_rect, } } impl ClipItemKind { pub fn new_box_shadow( shadow_rect_fract_offset: LayoutPoint, shadow_rect_size: LayoutSize, mut shadow_radius: BorderRadius, prim_shadow_rect: LayoutRect, blur_radius: f32, clip_mode: BoxShadowClipMode, ) -> Self { let mut source = compute_box_shadow_parameters( shadow_rect_fract_offset, shadow_rect_size, shadow_radius, prim_shadow_rect, blur_radius, clip_mode, ); fn needed_downscaling(source: &BoxShadowClipSource) -> Option { // This size is fairly arbitrary, but it's the same as the size that // we use to avoid caching big blurred stacking contexts. // // If you change it, ensure that the reftests // box-shadow-large-blur-radius-* still hit the downscaling path, // and that they render correctly. const MAX_SIZE: f32 = 2048.; let max_dimension = source.shadow_rect_alloc_size.width.max(source.shadow_rect_alloc_size.height); if max_dimension > MAX_SIZE { Some(MAX_SIZE / max_dimension) } else { None } } if let Some(downscale) = needed_downscaling(&source) { shadow_radius.bottom_left.height *= downscale; shadow_radius.bottom_left.width *= downscale; shadow_radius.bottom_right.height *= downscale; shadow_radius.bottom_right.width *= downscale; shadow_radius.top_left.height *= downscale; shadow_radius.top_left.width *= downscale; shadow_radius.top_right.height *= downscale; shadow_radius.top_right.width *= downscale; let original_alloc_size = source.shadow_rect_alloc_size; source = compute_box_shadow_parameters( shadow_rect_fract_offset * downscale, shadow_rect_size * downscale, shadow_radius, prim_shadow_rect, blur_radius * downscale, clip_mode, ); source.original_alloc_size = original_alloc_size; } ClipItemKind::BoxShadow { source } } /// Returns true if this clip mask can run through the fast path /// for the given clip item type. /// /// Note: this logic has to match `ClipBatcher::add` behavior. fn supports_fast_path_rendering(&self) -> bool { match *self { ClipItemKind::Rectangle { .. } | ClipItemKind::Image { .. } | ClipItemKind::BoxShadow { .. } => { false } ClipItemKind::RoundedRectangle { ref radius, .. } => { // The rounded clip rect fast path shader can only work // if the radii are uniform. radius.is_uniform().is_some() } } } // Get an optional clip rect that a clip source can provide to // reduce the size of a primitive region. This is typically // used to eliminate redundant clips, and reduce the size of // any clip mask that eventually gets drawn. pub fn get_local_clip_rect(&self) -> Option { match *self { ClipItemKind::Rectangle { rect, mode: ClipMode::Clip } => Some(rect), ClipItemKind::Rectangle { mode: ClipMode::ClipOut, .. } => None, ClipItemKind::RoundedRectangle { rect, mode: ClipMode::Clip, .. } => Some(rect), ClipItemKind::RoundedRectangle { mode: ClipMode::ClipOut, .. } => None, ClipItemKind::Image { rect, .. } => { Some(rect) } ClipItemKind::BoxShadow { .. } => None, } } fn get_clip_result_complex( &self, transform: &LayoutToWorldTransform, prim_world_rect: &WorldRect, world_rect: &WorldRect, ) -> ClipResult { let visible_rect = match prim_world_rect.intersection(world_rect) { Some(rect) => rect, None => return ClipResult::Reject, }; let (clip_rect, inner_rect, mode) = match *self { ClipItemKind::Rectangle { rect, mode } => { (rect, Some(rect), mode) } ClipItemKind::RoundedRectangle { rect, ref radius, mode } => { let inner_clip_rect = extract_inner_rect_safe(&rect, radius); (rect, inner_clip_rect, mode) } ClipItemKind::Image { rect, .. } => { (rect, None, ClipMode::Clip) } ClipItemKind::BoxShadow { .. } => { return ClipResult::Partial; } }; if let Some(ref inner_clip_rect) = inner_rect { if let Some(()) = projected_rect_contains(inner_clip_rect, transform, &visible_rect) { return match mode { ClipMode::Clip => ClipResult::Accept, ClipMode::ClipOut => ClipResult::Reject, }; } } match mode { ClipMode::Clip => { let outer_clip_rect = match project_rect( transform, &clip_rect, &world_rect, ) { Some(outer_clip_rect) => outer_clip_rect, None => return ClipResult::Partial, }; match outer_clip_rect.intersection(prim_world_rect) { Some(..) => { ClipResult::Partial } None => { ClipResult::Reject } } } ClipMode::ClipOut => ClipResult::Partial, } } // Check how a given clip source affects a local primitive region. fn get_clip_result( &self, prim_rect: &LayoutRect, ) -> ClipResult { match *self { ClipItemKind::Rectangle { rect, mode: ClipMode::Clip } => { if rect.contains_box(prim_rect) { return ClipResult::Accept; } match rect.intersection(prim_rect) { Some(..) => { ClipResult::Partial } None => { ClipResult::Reject } } } ClipItemKind::Rectangle { rect, mode: ClipMode::ClipOut } => { if rect.contains_box(prim_rect) { return ClipResult::Reject; } match rect.intersection(prim_rect) { Some(_) => { ClipResult::Partial } None => { ClipResult::Accept } } } ClipItemKind::RoundedRectangle { rect, ref radius, mode: ClipMode::Clip } => { // TODO(gw): Consider caching this in the ClipNode // if it ever shows in profiles. if rounded_rectangle_contains_box_quick(&rect, radius, &prim_rect) { return ClipResult::Accept; } match rect.intersection(prim_rect) { Some(..) => { ClipResult::Partial } None => { ClipResult::Reject } } } ClipItemKind::RoundedRectangle { rect, ref radius, mode: ClipMode::ClipOut } => { // TODO(gw): Consider caching this in the ClipNode // if it ever shows in profiles. if rounded_rectangle_contains_box_quick(&rect, radius, &prim_rect) { return ClipResult::Reject; } match rect.intersection(prim_rect) { Some(_) => { ClipResult::Partial } None => { ClipResult::Accept } } } ClipItemKind::Image { rect, .. } => { match rect.intersection(prim_rect) { Some(..) => { ClipResult::Partial } None => { ClipResult::Reject } } } ClipItemKind::BoxShadow { .. } => { ClipResult::Partial } } } } /// Represents a local rect and a device space /// rectangles that are either outside or inside bounds. #[derive(Clone, Debug, PartialEq)] pub struct Geometry { pub local_rect: LayoutRect, pub device_rect: DeviceIntRect, } impl From for Geometry { fn from(local_rect: LayoutRect) -> Self { Geometry { local_rect, device_rect: DeviceIntRect::zero(), } } } pub fn rounded_rectangle_contains_point( point: &LayoutPoint, rect: &LayoutRect, radii: &BorderRadius ) -> bool { if !rect.contains(*point) { return false; } let top_left_center = rect.min + radii.top_left.to_vector(); if top_left_center.x > point.x && top_left_center.y > point.y && !Ellipse::new(radii.top_left).contains(*point - top_left_center.to_vector()) { return false; } let bottom_right_center = rect.bottom_right() - radii.bottom_right.to_vector(); if bottom_right_center.x < point.x && bottom_right_center.y < point.y && !Ellipse::new(radii.bottom_right).contains(*point - bottom_right_center.to_vector()) { return false; } let top_right_center = rect.top_right() + LayoutVector2D::new(-radii.top_right.width, radii.top_right.height); if top_right_center.x < point.x && top_right_center.y > point.y && !Ellipse::new(radii.top_right).contains(*point - top_right_center.to_vector()) { return false; } let bottom_left_center = rect.bottom_left() + LayoutVector2D::new(radii.bottom_left.width, -radii.bottom_left.height); if bottom_left_center.x > point.x && bottom_left_center.y < point.y && !Ellipse::new(radii.bottom_left).contains(*point - bottom_left_center.to_vector()) { return false; } true } /// Return true if the rounded rectangle described by `container` and `radii` /// definitely contains `containee`. May return false negatives, but never false /// positives. fn rounded_rectangle_contains_box_quick( container: &LayoutRect, radii: &BorderRadius, containee: &LayoutRect, ) -> bool { if !container.contains_box(containee) { return false; } /// Return true if `point` falls within `corner`. This only covers the /// upper-left case; we transform the other corners into that form. fn foul(point: LayoutPoint, corner: LayoutPoint) -> bool { point.x < corner.x && point.y < corner.y } /// Flip `pt` about the y axis (i.e. negate `x`). fn flip_x(pt: LayoutPoint) -> LayoutPoint { LayoutPoint { x: -pt.x, .. pt } } /// Flip `pt` about the x axis (i.e. negate `y`). fn flip_y(pt: LayoutPoint) -> LayoutPoint { LayoutPoint { y: -pt.y, .. pt } } if foul(containee.top_left(), container.top_left() + radii.top_left) || foul(flip_x(containee.top_right()), flip_x(container.top_right()) + radii.top_right) || foul(flip_y(containee.bottom_left()), flip_y(container.bottom_left()) + radii.bottom_left) || foul(-containee.bottom_right(), -container.bottom_right() + radii.bottom_right) { return false; } true } /// Test where point p is relative to the infinite line that passes through the segment /// defined by p0 and p1. Point p is on the "left" of the line if the triangle (p0, p1, p) /// forms a counter-clockwise triangle. /// > 0 is left of the line /// < 0 is right of the line /// == 0 is on the line pub fn is_left_of_line( p_x: f32, p_y: f32, p0_x: f32, p0_y: f32, p1_x: f32, p1_y: f32, ) -> f32 { (p1_x - p0_x) * (p_y - p0_y) - (p_x - p0_x) * (p1_y - p0_y) } pub fn polygon_contains_point( point: &LayoutPoint, rect: &LayoutRect, polygon: &PolygonKey, ) -> bool { if !rect.contains(*point) { return false; } // p is a LayoutPoint that we'll be comparing to dimensionless PointKeys, // which were created from LayoutPoints, so it all works out. let p = LayoutPoint::new(point.x - rect.min.x, point.y - rect.min.y); // Calculate a winding number for this point. let mut winding_number: i32 = 0; let count = polygon.point_count as usize; for i in 0..count { let p0 = polygon.points[i]; let p1 = polygon.points[(i + 1) % count]; if p0.y <= p.y { if p1.y > p.y { if is_left_of_line(p.x, p.y, p0.x, p0.y, p1.x, p1.y) > 0.0 { winding_number = winding_number + 1; } } } else if p1.y <= p.y { if is_left_of_line(p.x, p.y, p0.x, p0.y, p1.x, p1.y) < 0.0 { winding_number = winding_number - 1; } } } match polygon.fill_rule { FillRule::Nonzero => winding_number != 0, FillRule::Evenodd => winding_number.abs() % 2 == 1, } } pub fn projected_rect_contains( source_rect: &LayoutRect, transform: &LayoutToWorldTransform, target_rect: &WorldRect, ) -> Option<()> { let points = [ transform.transform_point2d(source_rect.top_left())?, transform.transform_point2d(source_rect.top_right())?, transform.transform_point2d(source_rect.bottom_right())?, transform.transform_point2d(source_rect.bottom_left())?, ]; let target_points = [ target_rect.top_left(), target_rect.top_right(), target_rect.bottom_right(), target_rect.bottom_left(), ]; // iterate the edges of the transformed polygon for (a, b) in points .iter() .cloned() .zip(points[1..].iter().cloned().chain(iter::once(points[0]))) { // If this edge is redundant, it's a weird, case, and we shouldn't go // length in trying to take the fast path (e.g. when the whole rectangle is a point). // If any of edges of the target rectangle crosses the edge, it's not completely // inside our transformed polygon either. if a.approx_eq(&b) || target_points.iter().any(|&c| (b - a).cross(c - a) < 0.0) { return None } } Some(()) } // Add a clip node into the list of clips to be processed // for the current clip chain. Returns false if the clip // results in the entire primitive being culled out. fn add_clip_node_to_current_chain( handle: ClipDataHandle, prim_spatial_node_index: SpatialNodeIndex, pic_spatial_node_index: SpatialNodeIndex, local_clip_rect: &mut LayoutRect, clip_node_info: &mut Vec, pic_coverage_rect: &mut PictureRect, clip_data_store: &ClipDataStore, spatial_tree: &SpatialTree, ) -> bool { let clip_node = &clip_data_store[handle]; // Determine the most efficient way to convert between coordinate // systems of the primitive and clip node. let conversion = ClipSpaceConversion::new( prim_spatial_node_index, clip_node.item.spatial_node_index, spatial_tree, ); // If we can convert spaces, try to reduce the size of the region // requested, and cache the conversion information for the next step. if let Some(clip_rect) = clip_node.item.kind.get_local_clip_rect() { match conversion { ClipSpaceConversion::Local => { *local_clip_rect = match local_clip_rect.intersection(&clip_rect) { Some(rect) => rect, None => return false, }; } ClipSpaceConversion::ScaleOffset(ref scale_offset) => { let clip_rect = scale_offset.map_rect(&clip_rect); *local_clip_rect = match local_clip_rect.intersection(&clip_rect) { Some(rect) => rect, None => return false, }; } ClipSpaceConversion::Transform(..) => { // Map the local clip rect directly into the same space as the picture // surface. This will often be the same space as the clip itself, which // results in a reduction in allocated clip mask size. // For simplicity, only apply this optimization if the clip is in the // same coord system as the picture. There are some 'advanced' perspective // clip tests in wrench that break without this check. Those cases are // never used in Gecko, and we aim to remove support in WR for that // in future to simplify the clipping pipeline. let pic_coord_system = spatial_tree .get_spatial_node(pic_spatial_node_index) .coordinate_system_id; let clip_coord_system = spatial_tree .get_spatial_node(clip_node.item.spatial_node_index) .coordinate_system_id; if pic_coord_system == clip_coord_system { let mapper = SpaceMapper::new_with_target( pic_spatial_node_index, clip_node.item.spatial_node_index, PictureRect::max_rect(), spatial_tree, ); if let Some(pic_clip_rect) = mapper.map(&clip_rect) { *pic_coverage_rect = pic_clip_rect .intersection(pic_coverage_rect) .unwrap_or(PictureRect::zero()); } } } } } clip_node_info.push(ClipNodeInfo { conversion, handle, }); true } #[cfg(test)] mod tests { use super::projected_rect_contains; use euclid::{Transform3D, rect}; #[test] fn test_empty_projected_rect() { assert_eq!( None, projected_rect_contains( &rect(10.0, 10.0, 0.0, 0.0).to_box2d(), &Transform3D::identity(), &rect(20.0, 20.0, 10.0, 10.0).to_box2d(), ), "Empty rectangle is considered to include a non-empty!" ); } } /// PolygonKeys get interned, because it's a convenient way to move the data /// for the polygons out of the ClipItemKind and ClipItemKeyKind enums. The /// polygon data is both interned and retrieved by the scene builder, and not /// accessed at all by the frame builder. Another oddity is that the /// PolygonKey contains the totality of the information about the polygon, so /// the InternData and StoreData types are both PolygonKey. #[derive(Copy, Clone, Debug, Hash, MallocSizeOf, PartialEq, Eq)] #[cfg_attr(any(feature = "serde"), derive(Deserialize, Serialize))] pub enum PolygonIntern {} pub type PolygonDataHandle = intern::Handle; impl intern::InternDebug for PolygonKey {} impl intern::Internable for PolygonIntern { type Key = PolygonKey; type StoreData = PolygonKey; type InternData = PolygonKey; const PROFILE_COUNTER: usize = crate::profiler::INTERNED_POLYGONS; }