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