1 // Copyright 2016 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "third_party/blink/renderer/platform/graphics/paint/geometry_mapper.h"
6
7 #include "third_party/blink/renderer/platform/geometry/layout_rect.h"
8 #include "third_party/blink/renderer/platform/runtime_enabled_features.h"
9
10 namespace blink {
11
12 GeometryMapper::Translation2DOrMatrix
SourceToDestinationProjection(const TransformPaintPropertyNode & source,const TransformPaintPropertyNode & destination)13 GeometryMapper::SourceToDestinationProjection(
14 const TransformPaintPropertyNode& source,
15 const TransformPaintPropertyNode& destination) {
16 bool has_animation = false;
17 bool success = false;
18 return SourceToDestinationProjectionInternal(source, destination,
19 has_animation, success);
20 }
21
22 // Returns flatten(destination_to_screen)^-1 * flatten(source_to_screen)
23 //
24 // In case that source and destination are coplanar in tree hierarchy [1],
25 // computes destination_to_plane_root ^ -1 * source_to_plane_root.
26 // It can be proved that [2] the result will be the same (except numerical
27 // errors) when the plane root has invertible screen projection, and this
28 // offers fallback definition when plane root is singular. For example:
29 // <div style="transform:rotateY(90deg); overflow:scroll;">
30 // <div id="A" style="opacity:0.5;">
31 // <div id="B" style="position:absolute;"></div>
32 // </div>
33 // </div>
34 // Both A and B have non-invertible screen projection, nevertheless it is
35 // useful to define projection between A and B. Say, the transform may be
36 // animated in compositor thus become visible.
37 // As SPv1 treats 3D transforms as compositing trigger, that implies mappings
38 // within the same compositing layer can only contain 2D transforms, thus
39 // intra-composited-layer queries are guaranteed to be handled correctly.
40 //
41 // [1] As defined by that all local transforms between source and some common
42 // ancestor 'plane root' and all local transforms between the destination
43 // and the plane root being flat.
44 // [2] destination_to_screen = plane_root_to_screen * destination_to_plane_root
45 // source_to_screen = plane_root_to_screen * source_to_plane_root
46 // output = flatten(destination_to_screen)^-1 * flatten(source_to_screen)
47 // = flatten(plane_root_to_screen * destination_to_plane_root)^-1 *
48 // flatten(plane_root_to_screen * source_to_plane_root)
49 // Because both destination_to_plane_root and source_to_plane_root are
50 // already flat,
51 // = flatten(plane_root_to_screen * flatten(destination_to_plane_root))^-1 *
52 // flatten(plane_root_to_screen * flatten(source_to_plane_root))
53 // By flatten lemma [3] flatten(A * flatten(B)) = flatten(A) * flatten(B),
54 // = flatten(destination_to_plane_root)^-1 *
55 // flatten(plane_root_to_screen)^-1 *
56 // flatten(plane_root_to_screen) * flatten(source_to_plane_root)
57 // If flatten(plane_root_to_screen) is invertible, they cancel out:
58 // = flatten(destination_to_plane_root)^-1 * flatten(source_to_plane_root)
59 // = destination_to_plane_root^-1 * source_to_plane_root
60 // [3] Flatten lemma: https://goo.gl/DNKyOc
61 GeometryMapper::Translation2DOrMatrix
SourceToDestinationProjectionInternal(const TransformPaintPropertyNode & source,const TransformPaintPropertyNode & destination,bool & has_animation,bool & success)62 GeometryMapper::SourceToDestinationProjectionInternal(
63 const TransformPaintPropertyNode& source,
64 const TransformPaintPropertyNode& destination,
65 bool& has_animation,
66 bool& success) {
67 has_animation = false;
68 success = true;
69
70 if (&source == &destination)
71 return Translation2DOrMatrix();
72
73 if (source.Parent() && &destination == &source.Parent()->Unalias()) {
74 if (source.IsIdentityOr2DTranslation()) {
75 // We always use full matrix for animating transforms.
76 DCHECK(!source.HasActiveTransformAnimation());
77 return Translation2DOrMatrix(source.Translation2D());
78 }
79 // The result will be translate(origin)*matrix*translate(-origin) which
80 // equals to matrix if the origin is zero or if the matrix is just
81 // identity or 2d translation.
82 if (source.Origin().IsZero()) {
83 has_animation = source.HasActiveTransformAnimation();
84 return Translation2DOrMatrix(source.Matrix());
85 }
86 }
87
88 if (destination.IsIdentityOr2DTranslation() && destination.Parent() &&
89 &source == &destination.Parent()->Unalias()) {
90 // We always use full matrix for animating transforms.
91 DCHECK(!destination.HasActiveTransformAnimation());
92 return Translation2DOrMatrix(-destination.Translation2D());
93 }
94
95 const auto& source_cache = source.GetTransformCache();
96 const auto& destination_cache = destination.GetTransformCache();
97
98 // Case 1a (fast path of case 1b): check if source and destination are under
99 // the same 2d translation root.
100 if (source_cache.root_of_2d_translation() ==
101 destination_cache.root_of_2d_translation()) {
102 // We always use full matrix for animating transforms.
103 return Translation2DOrMatrix(source_cache.to_2d_translation_root() -
104 destination_cache.to_2d_translation_root());
105 }
106
107 // Case 1b: Check if source and destination are known to be coplanar.
108 // Even if destination may have invertible screen projection,
109 // this formula is likely to be numerically more stable.
110 if (source_cache.plane_root() == destination_cache.plane_root()) {
111 has_animation = source_cache.has_animation_to_plane_root() ||
112 destination_cache.has_animation_to_plane_root();
113 if (&source == destination_cache.plane_root()) {
114 return Translation2DOrMatrix(destination_cache.from_plane_root());
115 }
116 if (&destination == source_cache.plane_root()) {
117 return Translation2DOrMatrix(source_cache.to_plane_root());
118 }
119 TransformationMatrix matrix;
120 destination_cache.ApplyFromPlaneRoot(matrix);
121 source_cache.ApplyToPlaneRoot(matrix);
122 return Translation2DOrMatrix(matrix);
123 }
124
125 // Case 2: Check if we can fallback to the canonical definition of
126 // flatten(destination_to_screen)^-1 * flatten(source_to_screen)
127 // If flatten(destination_to_screen)^-1 is invalid, we are out of luck.
128 // Screen transform data are updated lazily because they are rarely used.
129 source.UpdateScreenTransform();
130 destination.UpdateScreenTransform();
131 has_animation = source_cache.has_animation_to_screen() ||
132 destination_cache.has_animation_to_screen();
133 if (!destination_cache.projection_from_screen_is_valid()) {
134 success = false;
135 return Translation2DOrMatrix();
136 }
137
138 // Case 3: Compute:
139 // flatten(destination_to_screen)^-1 * flatten(source_to_screen)
140 const auto& root = TransformPaintPropertyNode::Root();
141 if (&source == &root)
142 return Translation2DOrMatrix(destination_cache.projection_from_screen());
143 TransformationMatrix matrix;
144 destination_cache.ApplyProjectionFromScreen(matrix);
145 source_cache.ApplyToScreen(matrix);
146 matrix.FlattenTo2d();
147 return Translation2DOrMatrix(matrix);
148 }
149
LocalToAncestorVisualRect(const PropertyTreeState & local_state,const PropertyTreeState & ancestor_state,FloatClipRect & mapping_rect,OverlayScrollbarClipBehavior clip_behavior,InclusiveIntersectOrNot inclusive_behavior,ExpandVisualRectForAnimationOrNot expand_for_animation)150 bool GeometryMapper::LocalToAncestorVisualRect(
151 const PropertyTreeState& local_state,
152 const PropertyTreeState& ancestor_state,
153 FloatClipRect& mapping_rect,
154 OverlayScrollbarClipBehavior clip_behavior,
155 InclusiveIntersectOrNot inclusive_behavior,
156 ExpandVisualRectForAnimationOrNot expand_for_animation) {
157 bool success = false;
158 bool result = LocalToAncestorVisualRectInternal(
159 local_state, ancestor_state, mapping_rect, clip_behavior,
160 inclusive_behavior, expand_for_animation, success);
161 DCHECK(success);
162 return result;
163 }
164
LocalToAncestorVisualRectInternal(const PropertyTreeState & local_state,const PropertyTreeState & ancestor_state,FloatClipRect & rect_to_map,OverlayScrollbarClipBehavior clip_behavior,InclusiveIntersectOrNot inclusive_behavior,ExpandVisualRectForAnimationOrNot expand_for_animation,bool & success)165 bool GeometryMapper::LocalToAncestorVisualRectInternal(
166 const PropertyTreeState& local_state,
167 const PropertyTreeState& ancestor_state,
168 FloatClipRect& rect_to_map,
169 OverlayScrollbarClipBehavior clip_behavior,
170 InclusiveIntersectOrNot inclusive_behavior,
171 ExpandVisualRectForAnimationOrNot expand_for_animation,
172 bool& success) {
173 if (local_state == ancestor_state) {
174 success = true;
175 return true;
176 }
177
178 if (&local_state.Effect() != &ancestor_state.Effect()) {
179 return SlowLocalToAncestorVisualRectWithEffects(
180 local_state, ancestor_state, rect_to_map, clip_behavior,
181 inclusive_behavior, expand_for_animation, success);
182 }
183
184 bool has_animation = false;
185 const auto& translation_2d_or_matrix = SourceToDestinationProjectionInternal(
186 local_state.Transform(), ancestor_state.Transform(), has_animation,
187 success);
188 if (!success) {
189 // A failure implies either source-to-plane or destination-to-plane being
190 // singular. A notable example of singular source-to-plane from valid CSS:
191 // <div id="plane" style="transform:rotateY(180deg)">
192 // <div style="overflow:overflow">
193 // <div id="ancestor" style="opacity:0.5;">
194 // <div id="local" style="position:absolute; transform:scaleX(0);">
195 // </div>
196 // </div>
197 // </div>
198 // </div>
199 // Either way, the element won't be renderable thus returning empty rect.
200 success = true;
201 rect_to_map = FloatClipRect(FloatRect());
202 return false;
203 }
204
205 if (has_animation && expand_for_animation == kExpandVisualRectForAnimation) {
206 // Assume during the animation the transform can map |rect_to_map| to
207 // anywhere. Ancestor clips will still apply.
208 // TODO(crbug.com/1026653): Use animation bounds instead of infinite rect.
209 rect_to_map = InfiniteLooseFloatClipRect();
210 } else {
211 translation_2d_or_matrix.MapFloatClipRect(rect_to_map);
212 }
213
214 FloatClipRect clip_rect = LocalToAncestorClipRectInternal(
215 local_state.Clip(), ancestor_state.Clip(), ancestor_state.Transform(),
216 clip_behavior, inclusive_behavior, expand_for_animation, success);
217 if (success) {
218 // This is where we propagate the roundedness and tightness of |clip_rect|
219 // to |rect_to_map|.
220 if (inclusive_behavior == kInclusiveIntersect)
221 return rect_to_map.InclusiveIntersect(clip_rect);
222 rect_to_map.Intersect(clip_rect);
223 return !rect_to_map.Rect().IsEmpty();
224 }
225
226 if (!RuntimeEnabledFeatures::CompositeAfterPaintEnabled()) {
227 // On SPv1 we may fail when the paint invalidation container creates an
228 // overflow clip (in ancestor_state) which is not in localState of an
229 // out-of-flow positioned descendant. See crbug.com/513108 and web test
230 // compositing/overflow/handle-non-ancestor-clip-parent.html (run with
231 // --enable-prefer-compositing-to-lcd-text) for details.
232 // Ignore it for SPv1 for now.
233 success = true;
234 rect_to_map.ClearIsTight();
235 }
236 return !rect_to_map.Rect().IsEmpty();
237 }
238
SlowLocalToAncestorVisualRectWithEffects(const PropertyTreeState & local_state,const PropertyTreeState & ancestor_state,FloatClipRect & mapping_rect,OverlayScrollbarClipBehavior clip_behavior,InclusiveIntersectOrNot inclusive_behavior,ExpandVisualRectForAnimationOrNot expand_for_animation,bool & success)239 bool GeometryMapper::SlowLocalToAncestorVisualRectWithEffects(
240 const PropertyTreeState& local_state,
241 const PropertyTreeState& ancestor_state,
242 FloatClipRect& mapping_rect,
243 OverlayScrollbarClipBehavior clip_behavior,
244 InclusiveIntersectOrNot inclusive_behavior,
245 ExpandVisualRectForAnimationOrNot expand_for_animation,
246 bool& success) {
247 PropertyTreeState last_transform_and_clip_state(
248 local_state.Transform(), local_state.Clip(),
249 EffectPaintPropertyNode::Root());
250
251 const auto& ancestor_effect = ancestor_state.Effect();
252 for (const auto* effect = &local_state.Effect();
253 effect && effect != &ancestor_effect;
254 effect = effect->UnaliasedParent()) {
255 if (effect->HasActiveFilterAnimation() &&
256 expand_for_animation == kExpandVisualRectForAnimation) {
257 // Assume during the animation the filter can map |rect_to_map| to
258 // anywhere. Ancestor clips will still apply.
259 // TODO(crbug.com/1026653): Use animation bounds instead of infinite rect.
260 mapping_rect = InfiniteLooseFloatClipRect();
261 last_transform_and_clip_state.SetTransform(
262 effect->LocalTransformSpace().Unalias());
263 last_transform_and_clip_state.SetClip(effect->OutputClip()->Unalias());
264 continue;
265 }
266
267 if (!effect->HasFilterThatMovesPixels())
268 continue;
269
270 PropertyTreeState transform_and_clip_state(
271 effect->LocalTransformSpace().Unalias(),
272 effect->OutputClip()->Unalias(), EffectPaintPropertyNode::Root());
273 bool intersects = LocalToAncestorVisualRectInternal(
274 last_transform_and_clip_state, transform_and_clip_state, mapping_rect,
275 clip_behavior, inclusive_behavior, expand_for_animation, success);
276 if (!success || !intersects) {
277 success = true;
278 mapping_rect = FloatClipRect(FloatRect());
279 return false;
280 }
281
282 mapping_rect = FloatClipRect(effect->MapRect(mapping_rect.Rect()));
283 last_transform_and_clip_state = transform_and_clip_state;
284 }
285
286 PropertyTreeState final_transform_and_clip_state(
287 ancestor_state.Transform(), ancestor_state.Clip(),
288 EffectPaintPropertyNode::Root());
289 bool intersects = LocalToAncestorVisualRectInternal(
290 last_transform_and_clip_state, final_transform_and_clip_state,
291 mapping_rect, clip_behavior, inclusive_behavior, expand_for_animation,
292 success);
293
294 // Many effects (e.g. filters, clip-paths) can make a clip rect not tight.
295 mapping_rect.ClearIsTight();
296 return intersects;
297 }
298
LocalToAncestorClipRect(const PropertyTreeState & local_state,const PropertyTreeState & ancestor_state,OverlayScrollbarClipBehavior clip_behavior)299 FloatClipRect GeometryMapper::LocalToAncestorClipRect(
300 const PropertyTreeState& local_state,
301 const PropertyTreeState& ancestor_state,
302 OverlayScrollbarClipBehavior clip_behavior) {
303 const auto& local_clip = local_state.Clip();
304 const auto& ancestor_clip = ancestor_state.Clip();
305 if (&local_clip == &ancestor_clip)
306 return FloatClipRect();
307
308 bool success = false;
309 auto result = LocalToAncestorClipRectInternal(
310 local_clip, ancestor_clip, ancestor_state.Transform(), clip_behavior,
311 kNonInclusiveIntersect, kDontExpandVisualRectForAnimation, success);
312 DCHECK(success);
313
314 // Many effects (e.g. filters, clip-paths) can make a clip rect not tight.
315 if (&local_state.Effect() != &ancestor_state.Effect())
316 result.ClearIsTight();
317
318 return result;
319 }
320
GetClipRect(const ClipPaintPropertyNode & clip_node,OverlayScrollbarClipBehavior clip_behavior)321 static FloatClipRect GetClipRect(const ClipPaintPropertyNode& clip_node,
322 OverlayScrollbarClipBehavior clip_behavior) {
323 FloatClipRect clip_rect(
324 UNLIKELY(clip_behavior == kExcludeOverlayScrollbarSizeForHitTesting)
325 ? clip_node.UnsnappedClipRectExcludingOverlayScrollbars()
326 : FloatClipRect(clip_node.UnsnappedClipRect()));
327 if (clip_node.ClipPath())
328 clip_rect.ClearIsTight();
329 return clip_rect;
330 }
331
LocalToAncestorClipRectInternal(const ClipPaintPropertyNode & descendant_clip,const ClipPaintPropertyNode & ancestor_clip,const TransformPaintPropertyNode & ancestor_transform,OverlayScrollbarClipBehavior clip_behavior,InclusiveIntersectOrNot inclusive_behavior,ExpandVisualRectForAnimationOrNot expand_for_animation,bool & success)332 FloatClipRect GeometryMapper::LocalToAncestorClipRectInternal(
333 const ClipPaintPropertyNode& descendant_clip,
334 const ClipPaintPropertyNode& ancestor_clip,
335 const TransformPaintPropertyNode& ancestor_transform,
336 OverlayScrollbarClipBehavior clip_behavior,
337 InclusiveIntersectOrNot inclusive_behavior,
338 ExpandVisualRectForAnimationOrNot expand_for_animation,
339 bool& success) {
340 if (&descendant_clip == &ancestor_clip) {
341 success = true;
342 return FloatClipRect();
343 }
344 if (descendant_clip.UnaliasedParent() == &ancestor_clip &&
345 &descendant_clip.LocalTransformSpace() == &ancestor_transform) {
346 success = true;
347 return GetClipRect(descendant_clip, clip_behavior);
348 }
349
350 FloatClipRect clip;
351 const auto* clip_node = &descendant_clip;
352 Vector<const ClipPaintPropertyNode*> intermediate_nodes;
353
354 GeometryMapperClipCache::ClipAndTransform clip_and_transform(
355 &ancestor_clip, &ancestor_transform, clip_behavior);
356 // Iterate over the path from localState.clip to ancestor_state.clip. Stop if
357 // we've found a memoized (precomputed) clip for any particular node.
358 while (clip_node && clip_node != &ancestor_clip) {
359 const GeometryMapperClipCache::ClipCacheEntry* cached_clip = nullptr;
360 // Inclusive intersected clips are not cached at present.
361 if (inclusive_behavior != kInclusiveIntersect)
362 cached_clip = clip_node->GetClipCache().GetCachedClip(clip_and_transform);
363
364 if (cached_clip && cached_clip->has_transform_animation &&
365 expand_for_animation == kExpandVisualRectForAnimation) {
366 // Don't use cached clip if it's transformed by any animating transform.
367 cached_clip = nullptr;
368 }
369
370 if (cached_clip) {
371 clip = cached_clip->clip_rect;
372 break;
373 }
374
375 intermediate_nodes.push_back(clip_node);
376 clip_node = clip_node->UnaliasedParent();
377 }
378 if (!clip_node) {
379 success = false;
380 if (!RuntimeEnabledFeatures::CompositeAfterPaintEnabled()) {
381 // On SPv1 we may fail when the paint invalidation container creates an
382 // overflow clip (in ancestor_state) which is not in localState of an
383 // out-of-flow positioned descendant. See crbug.com/513108 and layout
384 // test compositing/overflow/handle-non-ancestor-clip-parent.html (run
385 // with --enable-prefer-compositing-to-lcd-text) for details.
386 // Ignore it for SPv1 for now.
387 success = true;
388 }
389 return InfiniteLooseFloatClipRect();
390 }
391
392 // Iterate down from the top intermediate node found in the previous loop,
393 // computing and memoizing clip rects as we go.
394 for (auto it = intermediate_nodes.rbegin(); it != intermediate_nodes.rend();
395 ++it) {
396 bool has_animation = false;
397 const auto& translation_2d_or_matrix =
398 SourceToDestinationProjectionInternal(
399 (*it)->LocalTransformSpace().Unalias(), ancestor_transform,
400 has_animation, success);
401 if (!success) {
402 success = true;
403 return FloatClipRect(FloatRect());
404 }
405
406 // Don't apply this clip if it's transformed by any animating transform.
407 if (has_animation && expand_for_animation == kExpandVisualRectForAnimation)
408 continue;
409
410 // This is where we generate the roundedness and tightness of clip rect
411 // from clip and transform properties, and propagate them to |clip|.
412 FloatClipRect mapped_rect(GetClipRect(**it, clip_behavior));
413 translation_2d_or_matrix.MapFloatClipRect(mapped_rect);
414 if (inclusive_behavior == kInclusiveIntersect) {
415 clip.InclusiveIntersect(mapped_rect);
416 } else {
417 clip.Intersect(mapped_rect);
418 // Inclusive intersected clips are not cached at present.
419 (*it)->GetClipCache().SetCachedClip(
420 GeometryMapperClipCache::ClipCacheEntry{clip_and_transform, clip,
421 has_animation});
422 }
423 }
424 // Clips that are inclusive intersected or expanded for animation are not
425 // cached at present.
426 DCHECK(inclusive_behavior == kInclusiveIntersect ||
427 expand_for_animation == kExpandVisualRectForAnimation ||
428 descendant_clip.GetClipCache()
429 .GetCachedClip(clip_and_transform)
430 ->clip_rect == clip);
431 success = true;
432 return clip;
433 }
434
ClearCache()435 void GeometryMapper::ClearCache() {
436 GeometryMapperTransformCache::ClearCache();
437 GeometryMapperClipCache::ClearCache();
438 }
439
440 } // namespace blink
441