gfx/wr/webrender/src/hit_test.rs

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 use api::{BorderRadius, ClipMode, HitTestItem, HitTestResult, ItemTag, PrimitiveFlags};
   6 use api::{PipelineId, ApiHitTester, ClipId};
   7 use api::units::*;
   8 use crate::clip::{ClipItemKind, ClipStore, ClipNode, rounded_rectangle_contains_point};
   9 use crate::clip::{polygon_contains_point};
  10 use crate::prim_store::PolygonKey;
  11 use crate::scene_builder_thread::Interners;
  12 use crate::spatial_tree::{SpatialNodeIndex, SpatialTree};
  13 use crate::internal_types::{FastHashMap, FastHashSet, LayoutPrimitiveInfo};
  14 use std::ops;
  15 use std::sync::{Arc, Mutex};
  16 use crate::util::{LayoutToWorldFastTransform, VecHelper};
  17
  18 pub struct SharedHitTester {
  19     // We don't really need a mutex here. We could do with some sort of
  20     // atomic-atomic-ref-counted pointer (an Arc which would let the pointer
  21     // be swapped atomically like an AtomicPtr).
  22     // In practive this shouldn't cause performance issues, though.
  23     hit_tester: Mutex<Arc<HitTester>>,
  24 }
  25
  26 impl SharedHitTester {
  27     pub fn new() -> Self {
  28         SharedHitTester {
  29             hit_tester: Mutex::new(Arc::new(HitTester::empty())),
  30         }
  31     }
  32
  33     pub fn get_ref(&self) -> Arc<HitTester> {
  34         let guard = self.hit_tester.lock().unwrap();
  35         Arc::clone(&*guard)
  36     }
  37
  38     pub(crate) fn update(&self, new_hit_tester: Arc<HitTester>) {
  39         let mut guard = self.hit_tester.lock().unwrap();
  40         *guard = new_hit_tester;
  41     }
  42 }
  43
  44 impl ApiHitTester for SharedHitTester {
  45     fn hit_test(&self,
  46         pipeline_id: Option<PipelineId>,
  47         point: WorldPoint,
  48     ) -> HitTestResult {
  49         self.get_ref().hit_test(HitTest::new(pipeline_id, point))
  50     }
  51 }
  52
  53 /// A copy of important spatial node data to use during hit testing. This a copy of
  54 /// data from the SpatialTree that will persist as a new frame is under construction,
  55 /// allowing hit tests consistent with the currently rendered frame.
  56 #[derive(MallocSizeOf)]
  57 struct HitTestSpatialNode {
  58     /// The pipeline id of this node.
  59     pipeline_id: PipelineId,
  60
  61     /// World transform for content transformed by this node.
  62     world_content_transform: LayoutToWorldFastTransform,
  63
  64     /// World viewport transform for content transformed by this node.
  65     world_viewport_transform: LayoutToWorldFastTransform,
  66
  67     /// The accumulated external scroll offset for this spatial node.
  68     external_scroll_offset: LayoutVector2D,
  69 }
  70
  71 #[derive(MallocSizeOf)]
  72 struct HitTestClipNode {
  73     /// A particular point must be inside all of these regions to be considered clipped in
  74     /// for the purposes of a hit test.
  75     region: HitTestRegion,
  76     /// The positioning node for this clip
  77     spatial_node_index: SpatialNodeIndex,
  78 }
  79
  80 impl HitTestClipNode {
  81     fn new(
  82         node: ClipNode,
  83         spatial_node_index: SpatialNodeIndex,
  84         interners: &Interners,
  85     ) -> Self {
  86         let region = match node.item.kind {
  87             ClipItemKind::Rectangle { rect, mode } => {
  88                 HitTestRegion::Rectangle(rect, mode)
  89             }
  90             ClipItemKind::RoundedRectangle { rect, radius, mode } => {
  91                 HitTestRegion::RoundedRectangle(rect, radius, mode)
  92             }
  93             ClipItemKind::Image { rect, polygon_handle, .. } => {
  94                 if let Some(handle) = polygon_handle {
  95                     // Retrieve the polygon data from the interner.
  96                     let polygon = &interners.polygon[handle];
  97                     HitTestRegion::Polygon(rect, *polygon)
  98                 } else {
  99                     HitTestRegion::Rectangle(rect, ClipMode::Clip)
 100                 }
 101             }
 102             ClipItemKind::BoxShadow { .. } => HitTestRegion::Invalid,
 103         };
 104
 105         HitTestClipNode {
 106             region,
 107             spatial_node_index,
 108         }
 109     }
 110 }
 111
 112 #[derive(Clone, MallocSizeOf)]
 113 struct HitTestingItem {
 114     rect: LayoutRect,
 115     clip_rect: LayoutRect,
 116     tag: ItemTag,
 117     is_backface_visible: bool,
 118     spatial_node_index: SpatialNodeIndex,
 119     #[ignore_malloc_size_of = "Range"]
 120     clip_nodes_range: ops::Range<ClipNodeIndex>,
 121 }
 122
 123 impl HitTestingItem {
 124     fn new(
 125         tag: ItemTag,
 126         info: &LayoutPrimitiveInfo,
 127         spatial_node_index: SpatialNodeIndex,
 128         clip_nodes_range: ops::Range<ClipNodeIndex>,
 129     ) -> HitTestingItem {
 130         HitTestingItem {
 131             rect: info.rect,
 132             clip_rect: info.clip_rect,
 133             tag,
 134             is_backface_visible: info.flags.contains(PrimitiveFlags::IS_BACKFACE_VISIBLE),
 135             spatial_node_index,
 136             clip_nodes_range,
 137         }
 138     }
 139 }
 140
 141 /// Statistics about allocation sizes of current hit tester,
 142 /// used to pre-allocate size of the next hit tester.
 143 pub struct HitTestingSceneStats {
 144     pub clip_nodes_count: usize,
 145     pub items_count: usize,
 146 }
 147
 148 impl HitTestingSceneStats {
 149     pub fn empty() -> Self {
 150         HitTestingSceneStats {
 151             clip_nodes_count: 0,
 152             items_count: 0,
 153         }
 154     }
 155 }
 156
 157 #[derive(MallocSizeOf, Debug, Copy, Clone)]
 158 pub struct ClipNodeIndex(u32);
 159
 160 /// Defines the immutable part of a hit tester for a given scene.
 161 /// The hit tester is recreated each time a frame is built, since
 162 /// it relies on the current values of the spatial tree.
 163 /// However, the clip chain and item definitions don't change,
 164 /// so they are created once per scene, and shared between
 165 /// hit tester instances via Arc.
 166 #[derive(MallocSizeOf)]
 167 pub struct HitTestingScene {
 168     /// Packed array of all hit test clip nodes
 169     clip_nodes: Vec<HitTestClipNode>,
 170
 171     /// List of hit testing primitives.
 172     items: Vec<HitTestingItem>,
 173
 174     /// Current stack of clip ids from stacking context
 175     #[ignore_malloc_size_of = "ClipId"]
 176     clip_id_stack: Vec<ClipId>,
 177
 178     /// Last cached clip id, useful for scenes with a lot
 179     /// of hit-test items that reference the same clip
 180     #[ignore_malloc_size_of = "simple"]
 181     cached_clip_id: Option<(ClipId, ops::Range<ClipNodeIndex>)>,
 182
 183     /// Temporary buffer used to de-duplicate clip ids when creating hit
 184     /// test clip nodes.
 185     #[ignore_malloc_size_of = "ClipId"]
 186     seen_clips: FastHashSet<ClipId>,
 187 }
 188
 189 impl HitTestingScene {
 190     /// Construct a new hit testing scene, pre-allocating to size
 191     /// provided by previous scene stats.
 192     pub fn new(stats: &HitTestingSceneStats) -> Self {
 193         HitTestingScene {
 194             clip_nodes: Vec::with_capacity(stats.clip_nodes_count),
 195             items: Vec::with_capacity(stats.items_count),
 196             clip_id_stack: Vec::with_capacity(8),
 197             cached_clip_id: None,
 198             seen_clips: FastHashSet::default(),
 199         }
 200     }
 201
 202     /// Get stats about the current scene allocation sizes.
 203     pub fn get_stats(&self) -> HitTestingSceneStats {
 204         HitTestingSceneStats {
 205             clip_nodes_count: self.clip_nodes.len(),
 206             items_count: self.items.len(),
 207         }
 208     }
 209
 210     /// Add a hit testing primitive.
 211     pub fn add_item(
 212         &mut self,
 213         tag: ItemTag,
 214         info: &LayoutPrimitiveInfo,
 215         spatial_node_index: SpatialNodeIndex,
 216         clip_id: ClipId,
 217         clip_store: &ClipStore,
 218         interners: &Interners,
 219     ) {
 220         let clip_range = match self.cached_clip_id {
 221             Some((cached_clip_id, ref range)) if cached_clip_id == clip_id => {
 222                 range.clone()
 223             }
 224             Some(_) | None => {
 225                 let start = ClipNodeIndex(self.clip_nodes.len() as u32);
 226
 227                 // Clear the set of which clip ids have been encountered for this item
 228                 self.seen_clips.clear();
 229
 230                 // Flatten all clips from the stacking context hierarchy
 231                 for clip_id in &self.clip_id_stack {
 232                     add_clips(
 233                         *clip_id,
 234                         clip_store,
 235                         &mut self.clip_nodes,
 236                         &mut self.seen_clips,
 237                         interners,
 238                     );
 239                 }
 240
 241                 // Add the primitive clip
 242                 add_clips(
 243                     clip_id,
 244                     clip_store,
 245                     &mut self.clip_nodes,
 246                     &mut self.seen_clips,
 247                     interners,
 248                 );
 249
 250                 let end = ClipNodeIndex(self.clip_nodes.len() as u32);
 251
 252                 let range = ops::Range {
 253                     start,
 254                     end,
 255                 };
 256
 257                 self.cached_clip_id = Some((clip_id, range.clone()));
 258
 259                 range
 260             }
 261         };
 262
 263         let item = HitTestingItem::new(
 264             tag,
 265             info,
 266             spatial_node_index,
 267             clip_range,
 268         );
 269
 270         self.items.push(item);
 271     }
 272
 273     /// Push a clip onto the current stack
 274     pub fn push_clip(
 275         &mut self,
 276         clip_id: ClipId,
 277     ) {
 278         // Invalidate the cache since the stack may affect the produced hit test clip struct
 279         self.cached_clip_id = None;
 280
 281         self.clip_id_stack.push(clip_id);
 282     }
 283
 284     /// Pop a clip from the current stack
 285     pub fn pop_clip(
 286         &mut self,
 287     ) {
 288         // Invalidate the cache since the stack may affect the produced hit test clip struct
 289         self.cached_clip_id = None;
 290
 291         self.clip_id_stack.pop().unwrap();
 292     }
 293 }
 294
 295 #[derive(MallocSizeOf)]
 296 enum HitTestRegion {
 297     Invalid,
 298     Rectangle(LayoutRect, ClipMode),
 299     RoundedRectangle(LayoutRect, BorderRadius, ClipMode),
 300     Polygon(LayoutRect, PolygonKey),
 301 }
 302
 303 impl HitTestRegion {
 304     fn contains(&self, point: &LayoutPoint) -> bool {
 305         match *self {
 306             HitTestRegion::Rectangle(ref rectangle, ClipMode::Clip) =>
 307                 rectangle.contains(*point),
 308             HitTestRegion::Rectangle(ref rectangle, ClipMode::ClipOut) =>
 309                 !rectangle.contains(*point),
 310             HitTestRegion::RoundedRectangle(rect, radii, ClipMode::Clip) =>
 311                 rounded_rectangle_contains_point(point, &rect, &radii),
 312             HitTestRegion::RoundedRectangle(rect, radii, ClipMode::ClipOut) =>
 313                 !rounded_rectangle_contains_point(point, &rect, &radii),
 314             HitTestRegion::Polygon(rect, polygon) =>
 315                 polygon_contains_point(point, &rect, &polygon),
 316             HitTestRegion::Invalid => true,
 317         }
 318     }
 319 }
 320
 321 #[derive(MallocSizeOf)]
 322 pub struct HitTester {
 323     #[ignore_malloc_size_of = "Arc"]
 324     scene: Arc<HitTestingScene>,
 325     spatial_nodes: Vec<HitTestSpatialNode>,
 326     pipeline_root_nodes: FastHashMap<PipelineId, SpatialNodeIndex>,
 327 }
 328
 329 impl HitTester {
 330     pub fn empty() -> Self {
 331         HitTester {
 332             scene: Arc::new(HitTestingScene::new(&HitTestingSceneStats::empty())),
 333             spatial_nodes: Vec::new(),
 334             pipeline_root_nodes: FastHashMap::default(),
 335         }
 336     }
 337
 338     pub fn new(
 339         scene: Arc<HitTestingScene>,
 340         spatial_tree: &SpatialTree,
 341     ) -> HitTester {
 342         let mut hit_tester = HitTester {
 343             scene,
 344             spatial_nodes: Vec::new(),
 345             pipeline_root_nodes: FastHashMap::default(),
 346         };
 347         hit_tester.read_spatial_tree(spatial_tree);
 348         hit_tester
 349     }
 350
 351     fn read_spatial_tree(
 352         &mut self,
 353         spatial_tree: &SpatialTree,
 354     ) {
 355         self.spatial_nodes.clear();
 356
 357         self.spatial_nodes.reserve(spatial_tree.spatial_nodes.len());
 358         for (index, node) in spatial_tree.spatial_nodes.iter().enumerate() {
 359             let index = SpatialNodeIndex::new(index);
 360
 361             // If we haven't already seen a node for this pipeline, record this one as the root
 362             // node.
 363             self.pipeline_root_nodes.entry(node.pipeline_id).or_insert(index);
 364
 365             //TODO: avoid inverting more than necessary:
 366             //  - if the coordinate system is non-invertible, no need to try any of these concrete transforms
 367             //  - if there are other places where inversion is needed, let's not repeat the step
 368
 369             self.spatial_nodes.push(HitTestSpatialNode {
 370                 pipeline_id: node.pipeline_id,
 371                 world_content_transform: spatial_tree
 372                     .get_world_transform(index)
 373                     .into_fast_transform(),
 374                 world_viewport_transform: spatial_tree
 375                     .get_world_viewport_transform(index)
 376                     .into_fast_transform(),
 377                 external_scroll_offset: spatial_tree.external_scroll_offset(index),
 378             });
 379         }
 380     }
 381
 382     pub fn hit_test(&self, test: HitTest) -> HitTestResult {
 383         let mut result = HitTestResult::default();
 384
 385         let mut current_spatial_node_index = SpatialNodeIndex::INVALID;
 386         let mut point_in_layer = None;
 387         let mut current_root_spatial_node_index = SpatialNodeIndex::INVALID;
 388         let mut point_in_viewport = None;
 389
 390         // For each hit test primitive
 391         for item in self.scene.items.iter().rev() {
 392             let scroll_node = &self.spatial_nodes[item.spatial_node_index.0 as usize];
 393             let pipeline_id = scroll_node.pipeline_id;
 394             match (test.pipeline_id, pipeline_id) {
 395                 (Some(id), node_id) if node_id != id => continue,
 396                 _ => {},
 397             }
 398
 399             // Update the cached point in layer space, if the spatial node
 400             // changed since last primitive.
 401             if item.spatial_node_index != current_spatial_node_index {
 402                 point_in_layer = scroll_node
 403                     .world_content_transform
 404                     .inverse()
 405                     .and_then(|inverted| inverted.transform_point2d(test.point));
 406                 current_spatial_node_index = item.spatial_node_index;
 407             }
 408
 409             // Only consider hit tests on transformable layers.
 410             if let Some(point_in_layer) = point_in_layer {
 411                 // If the item's rect or clip rect don't contain this point,
 412                 // it's not a valid hit.
 413                 if !item.rect.contains(point_in_layer) {
 414                     continue;
 415                 }
 416                 if !item.clip_rect.contains(point_in_layer) {
 417                     continue;
 418                 }
 419
 420                 // See if any of the clips for this primitive cull out the item.
 421                 let mut is_valid = true;
 422                 let clip_nodes = &self.scene.clip_nodes[item.clip_nodes_range.start.0 as usize .. item.clip_nodes_range.end.0 as usize];
 423                 for clip_node in clip_nodes {
 424                     let transform = self
 425                         .spatial_nodes[clip_node.spatial_node_index.0 as usize]
 426                         .world_content_transform;
 427                     let transformed_point = match transform
 428                         .inverse()
 429                         .and_then(|inverted| inverted.transform_point2d(test.point))
 430                     {
 431                         Some(point) => point,
 432                         None => {
 433                             continue;
 434                         }
 435                     };
 436                     if !clip_node.region.contains(&transformed_point) {
 437                         is_valid = false;
 438                         break;
 439                     }
 440                 }
 441                 if !is_valid {
 442                     continue;
 443                 }
 444
 445                 // Don't hit items with backface-visibility:hidden if they are facing the back.
 446                 if !item.is_backface_visible && scroll_node.world_content_transform.is_backface_visible() {
 447                     continue;
 448                 }
 449
 450                 // We need to calculate the position of the test point relative to the origin of
 451                 // the pipeline of the hit item. If we cannot get a transformed point, we are
 452                 // in a situation with an uninvertible transformation so we should just skip this
 453                 // result.
 454                 let root_spatial_node_index = self.pipeline_root_nodes[&pipeline_id];
 455                 if root_spatial_node_index != current_root_spatial_node_index {
 456                     let root_node = &self.spatial_nodes[root_spatial_node_index.0 as usize];
 457                     point_in_viewport = root_node
 458                         .world_viewport_transform
 459                         .inverse()
 460                         .and_then(|inverted| inverted.transform_point2d(test.point))
 461                         .map(|pt| pt - scroll_node.external_scroll_offset);
 462
 463                     current_root_spatial_node_index = root_spatial_node_index;
 464                 }
 465
 466                 if let Some(point_in_viewport) = point_in_viewport {
 467                     result.items.push(HitTestItem {
 468                         pipeline: pipeline_id,
 469                         tag: item.tag,
 470                         point_in_viewport,
 471                         point_relative_to_item: point_in_layer - item.rect.origin.to_vector(),
 472                     });
 473                 }
 474             }
 475         }
 476
 477         result.items.dedup();
 478         result
 479     }
 480 }
 481
 482 #[derive(MallocSizeOf)]
 483 pub struct HitTest {
 484     pipeline_id: Option<PipelineId>,
 485     point: WorldPoint,
 486 }
 487
 488 impl HitTest {
 489     pub fn new(
 490         pipeline_id: Option<PipelineId>,
 491         point: WorldPoint,
 492     ) -> HitTest {
 493         HitTest {
 494             pipeline_id,
 495             point,
 496         }
 497     }
 498 }
 499
 500 /// Collect clips for a given ClipId, convert and add them to the hit testing
 501 /// scene, if not already present.
 502 fn add_clips(
 503     clip_id: ClipId,
 504     clip_store: &ClipStore,
 505     clip_nodes: &mut Vec<HitTestClipNode>,
 506     seen_clips: &mut FastHashSet<ClipId>,
 507     interners: &Interners,
 508 ) {
 509     // If this clip-id has already been added to this hit-test item, skip it
 510     if seen_clips.contains(&clip_id) {
 511         return;
 512     }
 513     seen_clips.insert(clip_id);
 514
 515     let template = &clip_store.templates[&clip_id];
 516     let instances = &clip_store.instances[template.clips.start as usize .. template.clips.end as usize];
 517
 518     for clip in instances {
 519         clip_nodes.alloc().init(
 520             HitTestClipNode::new(
 521                 clip.key.into(),
 522                 clip.clip.spatial_node_index,
 523                 interners,
 524             )
 525         );
 526     }
 527
 528     // The ClipId parenting is terminated when we reach the root ClipId
 529     if clip_id != template.parent {
 530         add_clips(
 531             template.parent,
 532             clip_store,
 533             clip_nodes,
 534             seen_clips,
 535             interners,
 536         );
 537     }
 538 }