1// Copyright 2012 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 "cc/trees/occlusion_tracker.h"
6
7#include <algorithm>
8
9#include "cc/base/math_util.h"
10#include "cc/base/region.h"
11#include "cc/layers/layer.h"
12#include "cc/layers/layer_impl.h"
13#include "cc/layers/render_surface.h"
14#include "cc/layers/render_surface_impl.h"
15#include "ui/gfx/quad_f.h"
16#include "ui/gfx/rect_conversions.h"
17
18namespace cc {
19
20template <typename LayerType>
21OcclusionTracker<LayerType>::OcclusionTracker(
22    const gfx::Rect& screen_space_clip_rect)
23    : screen_space_clip_rect_(screen_space_clip_rect),
24      occluding_screen_space_rects_(NULL),
25      non_occluding_screen_space_rects_(NULL) {}
26
27template <typename LayerType>
28OcclusionTracker<LayerType>::~OcclusionTracker() {}
29
30template <typename LayerType>
31Occlusion OcclusionTracker<LayerType>::GetCurrentOcclusionForLayer(
32    const gfx::Transform& draw_transform) const {
33  DCHECK(!stack_.empty());
34  const StackObject& back = stack_.back();
35  return Occlusion(draw_transform,
36                   back.occlusion_from_outside_target,
37                   back.occlusion_from_inside_target);
38}
39
40template <typename LayerType>
41void OcclusionTracker<LayerType>::EnterLayer(
42    const LayerIteratorPosition<LayerType>& layer_iterator) {
43  LayerType* render_target = layer_iterator.target_render_surface_layer;
44
45  if (layer_iterator.represents_itself)
46    EnterRenderTarget(render_target);
47  else if (layer_iterator.represents_target_render_surface)
48    FinishedRenderTarget(render_target);
49}
50
51template <typename LayerType>
52void OcclusionTracker<LayerType>::LeaveLayer(
53    const LayerIteratorPosition<LayerType>& layer_iterator) {
54  LayerType* render_target = layer_iterator.target_render_surface_layer;
55
56  if (layer_iterator.represents_itself)
57    MarkOccludedBehindLayer(layer_iterator.current_layer);
58  // TODO(danakj): This should be done when entering the contributing surface,
59  // but in a way that the surface's own occlusion won't occlude itself.
60  else if (layer_iterator.represents_contributing_render_surface)
61    LeaveToRenderTarget(render_target);
62}
63
64template <typename RenderSurfaceType>
65static gfx::Rect ScreenSpaceClipRectInTargetSurface(
66    const RenderSurfaceType* target_surface,
67    const gfx::Rect& screen_space_clip_rect) {
68  gfx::Transform inverse_screen_space_transform(
69      gfx::Transform::kSkipInitialization);
70  if (!target_surface->screen_space_transform().GetInverse(
71          &inverse_screen_space_transform))
72    return target_surface->content_rect();
73
74  return MathUtil::ProjectEnclosingClippedRect(inverse_screen_space_transform,
75                                               screen_space_clip_rect);
76}
77
78template <typename RenderSurfaceType>
79static SimpleEnclosedRegion TransformSurfaceOpaqueRegion(
80    const SimpleEnclosedRegion& region,
81    bool have_clip_rect,
82    const gfx::Rect& clip_rect_in_new_target,
83    const gfx::Transform& transform) {
84  if (region.IsEmpty())
85    return region;
86
87  // Verify that rects within the |surface| will remain rects in its target
88  // surface after applying |transform|. If this is true, then apply |transform|
89  // to each rect within |region| in order to transform the entire Region.
90
91  // TODO(danakj): Find a rect interior to each transformed quad.
92  if (!transform.Preserves2dAxisAlignment())
93    return SimpleEnclosedRegion();
94
95  SimpleEnclosedRegion transformed_region;
96  for (size_t i = 0; i < region.GetRegionComplexity(); ++i) {
97    gfx::Rect transformed_rect =
98        MathUtil::MapEnclosedRectWith2dAxisAlignedTransform(transform,
99                                                            region.GetRect(i));
100    if (have_clip_rect)
101      transformed_rect.Intersect(clip_rect_in_new_target);
102    transformed_region.Union(transformed_rect);
103  }
104  return transformed_region;
105}
106
107static inline bool LayerOpacityKnown(const Layer* layer) {
108  return !layer->draw_opacity_is_animating();
109}
110static inline bool LayerOpacityKnown(const LayerImpl* layer) {
111  return true;
112}
113static inline bool LayerTransformsToTargetKnown(const Layer* layer) {
114  return !layer->draw_transform_is_animating();
115}
116static inline bool LayerTransformsToTargetKnown(const LayerImpl* layer) {
117  return true;
118}
119
120static inline bool SurfaceOpacityKnown(const RenderSurface* rs) {
121  return !rs->draw_opacity_is_animating();
122}
123static inline bool SurfaceOpacityKnown(const RenderSurfaceImpl* rs) {
124  return true;
125}
126static inline bool SurfaceTransformsToTargetKnown(const RenderSurface* rs) {
127  return !rs->target_surface_transforms_are_animating();
128}
129static inline bool SurfaceTransformsToTargetKnown(const RenderSurfaceImpl* rs) {
130  return true;
131}
132static inline bool SurfaceTransformsToScreenKnown(const RenderSurface* rs) {
133  return !rs->screen_space_transforms_are_animating();
134}
135static inline bool SurfaceTransformsToScreenKnown(const RenderSurfaceImpl* rs) {
136  return true;
137}
138
139static inline bool LayerIsInUnsorted3dRenderingContext(const Layer* layer) {
140  return layer->Is3dSorted();
141}
142static inline bool LayerIsInUnsorted3dRenderingContext(const LayerImpl* layer) {
143  return false;
144}
145
146template <typename LayerType>
147static inline bool LayerIsHidden(const LayerType* layer) {
148  return layer->hide_layer_and_subtree() ||
149         (layer->parent() && LayerIsHidden(layer->parent()));
150}
151
152template <typename LayerType>
153void OcclusionTracker<LayerType>::EnterRenderTarget(
154    const LayerType* new_target) {
155  if (!stack_.empty() && stack_.back().target == new_target)
156    return;
157
158  const LayerType* old_target = NULL;
159  const typename LayerType::RenderSurfaceType* old_occlusion_immune_ancestor =
160      NULL;
161  if (!stack_.empty()) {
162    old_target = stack_.back().target;
163    old_occlusion_immune_ancestor =
164        old_target->render_surface()->nearest_occlusion_immune_ancestor();
165  }
166  const typename LayerType::RenderSurfaceType* new_occlusion_immune_ancestor =
167      new_target->render_surface()->nearest_occlusion_immune_ancestor();
168
169  stack_.push_back(StackObject(new_target));
170
171  // We copy the screen occlusion into the new RenderSurface subtree, but we
172  // never copy in the occlusion from inside the target, since we are looking
173  // at a new RenderSurface target.
174
175  // If entering an unoccluded subtree, do not carry forward the outside
176  // occlusion calculated so far.
177  bool entering_unoccluded_subtree =
178      new_occlusion_immune_ancestor &&
179      new_occlusion_immune_ancestor != old_occlusion_immune_ancestor;
180
181  bool have_transform_from_screen_to_new_target = false;
182  gfx::Transform inverse_new_target_screen_space_transform(
183      // Note carefully, not used if screen space transform is uninvertible.
184      gfx::Transform::kSkipInitialization);
185  if (SurfaceTransformsToScreenKnown(new_target->render_surface())) {
186    have_transform_from_screen_to_new_target =
187        new_target->render_surface()->screen_space_transform().GetInverse(
188            &inverse_new_target_screen_space_transform);
189  }
190
191  bool entering_root_target = new_target->parent() == NULL;
192
193  bool copy_outside_occlusion_forward =
194      stack_.size() > 1 &&
195      !entering_unoccluded_subtree &&
196      have_transform_from_screen_to_new_target &&
197      !entering_root_target;
198  if (!copy_outside_occlusion_forward)
199    return;
200
201  int last_index = stack_.size() - 1;
202  gfx::Transform old_target_to_new_target_transform(
203      inverse_new_target_screen_space_transform,
204      old_target->render_surface()->screen_space_transform());
205  stack_[last_index].occlusion_from_outside_target =
206      TransformSurfaceOpaqueRegion<typename LayerType::RenderSurfaceType>(
207          stack_[last_index - 1].occlusion_from_outside_target,
208          false,
209          gfx::Rect(),
210          old_target_to_new_target_transform);
211  stack_[last_index].occlusion_from_outside_target.Union(
212      TransformSurfaceOpaqueRegion<typename LayerType::RenderSurfaceType>(
213          stack_[last_index - 1].occlusion_from_inside_target,
214          false,
215          gfx::Rect(),
216          old_target_to_new_target_transform));
217}
218
219template <typename LayerType>
220void OcclusionTracker<LayerType>::FinishedRenderTarget(
221    const LayerType* finished_target) {
222  // Make sure we know about the target surface.
223  EnterRenderTarget(finished_target);
224
225  typename LayerType::RenderSurfaceType* surface =
226      finished_target->render_surface();
227
228  // Readbacks always happen on render targets so we only need to check
229  // for readbacks here.
230  bool target_is_only_for_copy_request =
231      finished_target->HasCopyRequest() && LayerIsHidden(finished_target);
232
233  // If the occlusion within the surface can not be applied to things outside of
234  // the surface's subtree, then clear the occlusion here so it won't be used.
235  if (finished_target->mask_layer() || !SurfaceOpacityKnown(surface) ||
236      surface->draw_opacity() < 1 ||
237      !finished_target->uses_default_blend_mode() ||
238      target_is_only_for_copy_request ||
239      finished_target->filters().HasFilterThatAffectsOpacity()) {
240    stack_.back().occlusion_from_outside_target.Clear();
241    stack_.back().occlusion_from_inside_target.Clear();
242  } else if (!SurfaceTransformsToTargetKnown(surface)) {
243    stack_.back().occlusion_from_inside_target.Clear();
244    stack_.back().occlusion_from_outside_target.Clear();
245  }
246}
247
248template <typename LayerType>
249static void ReduceOcclusionBelowSurface(
250    LayerType* contributing_layer,
251    const gfx::Rect& surface_rect,
252    const gfx::Transform& surface_transform,
253    LayerType* render_target,
254    SimpleEnclosedRegion* occlusion_from_inside_target) {
255  if (surface_rect.IsEmpty())
256    return;
257
258  gfx::Rect affected_area_in_target =
259      MathUtil::MapEnclosingClippedRect(surface_transform, surface_rect);
260  if (contributing_layer->render_surface()->is_clipped()) {
261    affected_area_in_target.Intersect(
262        contributing_layer->render_surface()->clip_rect());
263  }
264  if (affected_area_in_target.IsEmpty())
265    return;
266
267  int outset_top, outset_right, outset_bottom, outset_left;
268  contributing_layer->background_filters().GetOutsets(
269      &outset_top, &outset_right, &outset_bottom, &outset_left);
270
271  // The filter can move pixels from outside of the clip, so allow affected_area
272  // to expand outside the clip.
273  affected_area_in_target.Inset(
274      -outset_left, -outset_top, -outset_right, -outset_bottom);
275  SimpleEnclosedRegion affected_occlusion = *occlusion_from_inside_target;
276  affected_occlusion.Intersect(affected_area_in_target);
277
278  occlusion_from_inside_target->Subtract(affected_area_in_target);
279  for (size_t i = 0; i < affected_occlusion.GetRegionComplexity(); ++i) {
280    gfx::Rect occlusion_rect = affected_occlusion.GetRect(i);
281
282    // Shrink the rect by expanding the non-opaque pixels outside the rect.
283
284    // The left outset of the filters moves pixels on the right side of
285    // the occlusion_rect into it, shrinking its right edge.
286    int shrink_left =
287        occlusion_rect.x() == affected_area_in_target.x() ? 0 : outset_right;
288    int shrink_top =
289        occlusion_rect.y() == affected_area_in_target.y() ? 0 : outset_bottom;
290    int shrink_right =
291        occlusion_rect.right() == affected_area_in_target.right() ?
292        0 : outset_left;
293    int shrink_bottom =
294        occlusion_rect.bottom() == affected_area_in_target.bottom() ?
295        0 : outset_top;
296
297    occlusion_rect.Inset(shrink_left, shrink_top, shrink_right, shrink_bottom);
298
299    occlusion_from_inside_target->Union(occlusion_rect);
300  }
301}
302
303template <typename LayerType>
304void OcclusionTracker<LayerType>::LeaveToRenderTarget(
305    const LayerType* new_target) {
306  int last_index = stack_.size() - 1;
307  bool surface_will_be_at_top_after_pop =
308      stack_.size() > 1 && stack_[last_index - 1].target == new_target;
309
310  // We merge the screen occlusion from the current RenderSurfaceImpl subtree
311  // out to its parent target RenderSurfaceImpl. The target occlusion can be
312  // merged out as well but needs to be transformed to the new target.
313
314  const LayerType* old_target = stack_[last_index].target;
315  const typename LayerType::RenderSurfaceType* old_surface =
316      old_target->render_surface();
317
318  SimpleEnclosedRegion old_occlusion_from_inside_target_in_new_target =
319      TransformSurfaceOpaqueRegion<typename LayerType::RenderSurfaceType>(
320          stack_[last_index].occlusion_from_inside_target,
321          old_surface->is_clipped(),
322          old_surface->clip_rect(),
323          old_surface->draw_transform());
324  if (old_target->has_replica() && !old_target->replica_has_mask()) {
325    old_occlusion_from_inside_target_in_new_target.Union(
326        TransformSurfaceOpaqueRegion<typename LayerType::RenderSurfaceType>(
327            stack_[last_index].occlusion_from_inside_target,
328            old_surface->is_clipped(),
329            old_surface->clip_rect(),
330            old_surface->replica_draw_transform()));
331  }
332
333  SimpleEnclosedRegion old_occlusion_from_outside_target_in_new_target =
334      TransformSurfaceOpaqueRegion<typename LayerType::RenderSurfaceType>(
335          stack_[last_index].occlusion_from_outside_target,
336          false,
337          gfx::Rect(),
338          old_surface->draw_transform());
339
340  gfx::Rect unoccluded_surface_rect;
341  gfx::Rect unoccluded_replica_rect;
342  if (old_target->background_filters().HasFilterThatMovesPixels()) {
343    unoccluded_surface_rect = UnoccludedContributingSurfaceContentRect(
344        old_surface->content_rect(), old_surface->draw_transform());
345    if (old_target->has_replica()) {
346      unoccluded_replica_rect = UnoccludedContributingSurfaceContentRect(
347          old_surface->content_rect(),
348          old_surface->replica_draw_transform());
349    }
350  }
351
352  if (surface_will_be_at_top_after_pop) {
353    // Merge the top of the stack down.
354    stack_[last_index - 1].occlusion_from_inside_target.Union(
355        old_occlusion_from_inside_target_in_new_target);
356    // TODO(danakj): Strictly this should subtract the inside target occlusion
357    // before union.
358    if (new_target->parent()) {
359      stack_[last_index - 1].occlusion_from_outside_target.Union(
360          old_occlusion_from_outside_target_in_new_target);
361    }
362    stack_.pop_back();
363  } else {
364    // Replace the top of the stack with the new pushed surface.
365    stack_.back().target = new_target;
366    stack_.back().occlusion_from_inside_target =
367        old_occlusion_from_inside_target_in_new_target;
368    if (new_target->parent()) {
369      stack_.back().occlusion_from_outside_target =
370          old_occlusion_from_outside_target_in_new_target;
371    } else {
372      stack_.back().occlusion_from_outside_target.Clear();
373    }
374  }
375
376  if (!old_target->background_filters().HasFilterThatMovesPixels())
377    return;
378
379  ReduceOcclusionBelowSurface(old_target,
380                              unoccluded_surface_rect,
381                              old_surface->draw_transform(),
382                              new_target,
383                              &stack_.back().occlusion_from_inside_target);
384  ReduceOcclusionBelowSurface(old_target,
385                              unoccluded_surface_rect,
386                              old_surface->draw_transform(),
387                              new_target,
388                              &stack_.back().occlusion_from_outside_target);
389
390  if (!old_target->has_replica())
391    return;
392  ReduceOcclusionBelowSurface(old_target,
393                              unoccluded_replica_rect,
394                              old_surface->replica_draw_transform(),
395                              new_target,
396                              &stack_.back().occlusion_from_inside_target);
397  ReduceOcclusionBelowSurface(old_target,
398                              unoccluded_replica_rect,
399                              old_surface->replica_draw_transform(),
400                              new_target,
401                              &stack_.back().occlusion_from_outside_target);
402}
403
404template <typename LayerType>
405void OcclusionTracker<LayerType>::MarkOccludedBehindLayer(
406    const LayerType* layer) {
407  DCHECK(!stack_.empty());
408  DCHECK_EQ(layer->render_target(), stack_.back().target);
409
410  if (!LayerOpacityKnown(layer) || layer->draw_opacity() < 1)
411    return;
412
413  if (!layer->uses_default_blend_mode())
414    return;
415
416  if (LayerIsInUnsorted3dRenderingContext(layer))
417    return;
418
419  if (!LayerTransformsToTargetKnown(layer))
420    return;
421
422  SimpleEnclosedRegion opaque_contents = layer->VisibleContentOpaqueRegion();
423  if (opaque_contents.IsEmpty())
424    return;
425
426  DCHECK(layer->visible_content_rect().Contains(opaque_contents.bounds()));
427
428  // TODO(danakj): Find a rect interior to each transformed quad.
429  if (!layer->draw_transform().Preserves2dAxisAlignment())
430    return;
431
432  gfx::Rect clip_rect_in_target = ScreenSpaceClipRectInTargetSurface(
433      layer->render_target()->render_surface(), screen_space_clip_rect_);
434  if (layer->is_clipped()) {
435    clip_rect_in_target.Intersect(layer->clip_rect());
436  } else {
437    clip_rect_in_target.Intersect(
438        layer->render_target()->render_surface()->content_rect());
439  }
440
441  for (size_t i = 0; i < opaque_contents.GetRegionComplexity(); ++i) {
442    gfx::Rect transformed_rect =
443        MathUtil::MapEnclosedRectWith2dAxisAlignedTransform(
444            layer->draw_transform(), opaque_contents.GetRect(i));
445    transformed_rect.Intersect(clip_rect_in_target);
446    if (transformed_rect.width() < minimum_tracking_size_.width() &&
447        transformed_rect.height() < minimum_tracking_size_.height())
448      continue;
449    stack_.back().occlusion_from_inside_target.Union(transformed_rect);
450
451    if (!occluding_screen_space_rects_)
452      continue;
453
454    // Save the occluding area in screen space for debug visualization.
455    bool clipped;
456    gfx::QuadF screen_space_quad = MathUtil::MapQuad(
457        layer->render_target()->render_surface()->screen_space_transform(),
458        gfx::QuadF(transformed_rect), &clipped);
459    // TODO(danakj): Store the quad in the debug info instead of the bounding
460    // box.
461    gfx::Rect screen_space_rect =
462        gfx::ToEnclosedRect(screen_space_quad.BoundingBox());
463    occluding_screen_space_rects_->push_back(screen_space_rect);
464  }
465
466  if (!non_occluding_screen_space_rects_)
467    return;
468
469  Region non_opaque_contents(gfx::Rect(layer->content_bounds()));
470  non_opaque_contents.Subtract(opaque_contents);
471
472  for (Region::Iterator non_opaque_content_rects(non_opaque_contents);
473       non_opaque_content_rects.has_rect();
474       non_opaque_content_rects.next()) {
475    gfx::Rect transformed_rect =
476        MathUtil::MapEnclosedRectWith2dAxisAlignedTransform(
477            layer->draw_transform(), non_opaque_content_rects.rect());
478    transformed_rect.Intersect(clip_rect_in_target);
479    if (transformed_rect.IsEmpty())
480      continue;
481
482    bool clipped;
483    gfx::QuadF screen_space_quad = MathUtil::MapQuad(
484        layer->render_target()->render_surface()->screen_space_transform(),
485        gfx::QuadF(transformed_rect),
486        &clipped);
487    // TODO(danakj): Store the quad in the debug info instead of the bounding
488    // box.
489    gfx::Rect screen_space_rect =
490        gfx::ToEnclosedRect(screen_space_quad.BoundingBox());
491    non_occluding_screen_space_rects_->push_back(screen_space_rect);
492  }
493}
494
495template <typename LayerType>
496gfx::Rect OcclusionTracker<LayerType>::UnoccludedContributingSurfaceContentRect(
497    const gfx::Rect& content_rect,
498    const gfx::Transform& draw_transform) const {
499  if (content_rect.IsEmpty())
500    return content_rect;
501
502  // A contributing surface doesn't get occluded by things inside its own
503  // surface, so only things outside the surface can occlude it. That occlusion
504  // is found just below the top of the stack (if it exists).
505  bool has_occlusion = stack_.size() > 1;
506  if (!has_occlusion)
507    return content_rect;
508
509  const StackObject& second_last = stack_[stack_.size() - 2];
510  if (second_last.occlusion_from_inside_target.IsEmpty() &&
511      second_last.occlusion_from_outside_target.IsEmpty())
512    return content_rect;
513
514  gfx::Transform inverse_draw_transform(gfx::Transform::kSkipInitialization);
515  bool ok = draw_transform.GetInverse(&inverse_draw_transform);
516  DCHECK(ok);
517
518  // Take the ToEnclosingRect at each step, as we want to contain any unoccluded
519  // partial pixels in the resulting Rect.
520  gfx::Rect unoccluded_rect_in_target_surface =
521      MathUtil::MapEnclosingClippedRect(draw_transform, content_rect);
522  DCHECK_LE(second_last.occlusion_from_inside_target.GetRegionComplexity(), 1u);
523  DCHECK_LE(second_last.occlusion_from_outside_target.GetRegionComplexity(),
524            1u);
525  // These subtract operations are more lossy than if we did both operations at
526  // once.
527  unoccluded_rect_in_target_surface.Subtract(
528      second_last.occlusion_from_inside_target.bounds());
529  unoccluded_rect_in_target_surface.Subtract(
530      second_last.occlusion_from_outside_target.bounds());
531
532  if (unoccluded_rect_in_target_surface.IsEmpty())
533    return gfx::Rect();
534
535  gfx::Rect unoccluded_rect = MathUtil::ProjectEnclosingClippedRect(
536      inverse_draw_transform, unoccluded_rect_in_target_surface);
537  unoccluded_rect.Intersect(content_rect);
538
539  return unoccluded_rect;
540}
541
542template <typename LayerType>
543Region OcclusionTracker<LayerType>::ComputeVisibleRegionInScreen() const {
544  DCHECK(!stack_.back().target->parent());
545  const SimpleEnclosedRegion& occluded =
546      stack_.back().occlusion_from_inside_target;
547  Region visible_region(screen_space_clip_rect_);
548  for (size_t i = 0; i < occluded.GetRegionComplexity(); ++i)
549    visible_region.Subtract(occluded.GetRect(i));
550  return visible_region;
551}
552
553// Instantiate (and export) templates here for the linker.
554template class OcclusionTracker<Layer>;
555template class OcclusionTracker<LayerImpl>;
556
557}  // namespace cc
558