patch from issue 218843002

This is another attempt to merge the R*Tree bounding boxes CL, after the first
one got kicked back by ASAN/LSAN bots. The leak has been repaired.

BUG=353867

Review URL: https://codereview.chromium.org/275183002

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@269883 0039d316-1c4b-4281-b951-d872f2087c98

39 files changed, 628 insertions, 100 deletions

diff --git a/ash/system/user/user_view.cc b/ash/system/user/user_view.cc
index 6707686..289da28 100644
--- a/ash/system/user/user_view.cc
+++ b/ash/system/user/user_view.cc
@@ -95,10 +95,11 @@ class LogoutButton : public TrayPopupLabelButton {
   virtual ~LogoutButton() {}
 
  private:
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE {
+  virtual void Paint(gfx::Canvas* canvas,
+                     const views::CullSet& cull_set) OVERRIDE {
     // Just skip paint if this button used as a placeholder.
     if (!placeholder_)
-      TrayPopupLabelButton::Paint(canvas);
+      TrayPopupLabelButton::Paint(canvas, cull_set);
   }
 
   bool placeholder_;
diff --git a/chrome/browser/ui/views/autofill/autofill_dialog_views.cc b/chrome/browser/ui/views/autofill/autofill_dialog_views.cc
index 6168bef..ec42f5c 100644
--- a/chrome/browser/ui/views/autofill/autofill_dialog_views.cc
+++ b/chrome/browser/ui/views/autofill/autofill_dialog_views.cc
@@ -692,7 +692,7 @@ void AutofillDialogViews::OverlayView::OnPaint(gfx::Canvas* canvas) {
     canvas->DrawPath(arrow, paint);
   }
 
-  PaintChildren(canvas);
+  PaintChildren(canvas, views::CullSet());
 }
 
 void AutofillDialogViews::OverlayView::OnNativeThemeChanged(
@@ -767,11 +767,13 @@ const char* AutofillDialogViews::NotificationArea::GetClassName() const {
 }
 
 void AutofillDialogViews::NotificationArea::PaintChildren(
-    gfx::Canvas* canvas) {}
+    gfx::Canvas* canvas,
+    const views::CullSet& cull_set) {
+}
 
 void AutofillDialogViews::NotificationArea::OnPaint(gfx::Canvas* canvas) {
   views::View::OnPaint(canvas);
-  views::View::PaintChildren(canvas);
+  views::View::PaintChildren(canvas, views::CullSet());
 
   if (HasArrow()) {
     DrawArrow(
@@ -1003,7 +1005,10 @@ const char* AutofillDialogViews::SuggestedButton::GetClassName() const {
   return kSuggestedButtonClassName;
 }
 
-void AutofillDialogViews::SuggestedButton::PaintChildren(gfx::Canvas* canvas) {}
+void AutofillDialogViews::SuggestedButton::PaintChildren(
+    gfx::Canvas* canvas,
+    const views::CullSet& cull_set) {
+}
 
 void AutofillDialogViews::SuggestedButton::OnPaint(gfx::Canvas* canvas) {
   ui::ResourceBundle& rb = ui::ResourceBundle::GetSharedInstance();
diff --git a/chrome/browser/ui/views/autofill/autofill_dialog_views.h b/chrome/browser/ui/views/autofill/autofill_dialog_views.h
index e84a880..ddadf14 100644
--- a/chrome/browser/ui/views/autofill/autofill_dialog_views.h
+++ b/chrome/browser/ui/views/autofill/autofill_dialog_views.h
@@ -261,7 +261,8 @@ class AutofillDialogViews : public AutofillDialogView,
     // views::View implementation.
     virtual gfx::Size GetPreferredSize() OVERRIDE;
     virtual const char* GetClassName() const OVERRIDE;
-    virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+    virtual void PaintChildren(gfx::Canvas* canvas,
+                               const views::CullSet& cull_set) OVERRIDE;
     virtual void OnPaint(gfx::Canvas* canvas) OVERRIDE;
 
     void set_arrow_centering_anchor(
@@ -341,7 +342,8 @@ class AutofillDialogViews : public AutofillDialogView,
     // views::MenuButton implementation.
     virtual gfx::Size GetPreferredSize() OVERRIDE;
     virtual const char* GetClassName() const OVERRIDE;
-    virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+    virtual void PaintChildren(gfx::Canvas* canvas,
+                               const views::CullSet& cull_set) OVERRIDE;
     virtual void OnPaint(gfx::Canvas* canvas) OVERRIDE;
 
    private:
diff --git a/chrome/browser/ui/views/bookmarks/bookmark_bar_view.cc b/chrome/browser/ui/views/bookmarks/bookmark_bar_view.cc
index 08973c8..fce7df8 100644
--- a/chrome/browser/ui/views/bookmarks/bookmark_bar_view.cc
+++ b/chrome/browser/ui/views/bookmarks/bookmark_bar_view.cc
@@ -738,8 +738,9 @@ void BookmarkBarView::ViewHierarchyChanged(
   }
 }
 
-void BookmarkBarView::PaintChildren(gfx::Canvas* canvas) {
-  View::PaintChildren(canvas);
+void BookmarkBarView::PaintChildren(gfx::Canvas* canvas,
+                                    const views::CullSet& cull_set) {
+  View::PaintChildren(canvas, cull_set);
 
   if (drop_info_.get() && drop_info_->valid &&
       drop_info_->location.operation != 0 && drop_info_->location.index != -1 &&
diff --git a/chrome/browser/ui/views/bookmarks/bookmark_bar_view.h b/chrome/browser/ui/views/bookmarks/bookmark_bar_view.h
index b13acaf..90a51e2 100644
--- a/chrome/browser/ui/views/bookmarks/bookmark_bar_view.h
+++ b/chrome/browser/ui/views/bookmarks/bookmark_bar_view.h
@@ -170,7 +170,8 @@ class BookmarkBarView : public DetachableToolbarView,
   virtual void Layout() OVERRIDE;
   virtual void ViewHierarchyChanged(
       const ViewHierarchyChangedDetails& details) OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
   virtual bool GetDropFormats(
       int* formats,
       std::set<ui::OSExchangeData::CustomFormat>* custom_formats) OVERRIDE;
diff --git a/chrome/browser/ui/views/frame/browser_view.cc b/chrome/browser/ui/views/frame/browser_view.cc
index 52f8024..969869f 100644
--- a/chrome/browser/ui/views/frame/browser_view.cc
+++ b/chrome/browser/ui/views/frame/browser_view.cc
@@ -1784,16 +1784,17 @@ void BrowserView::Layout() {
   toolbar_->location_bar()->omnibox_view()->SetFocusable(IsToolbarVisible());
 }
 
-void BrowserView::PaintChildren(gfx::Canvas* canvas) {
+void BrowserView::PaintChildren(gfx::Canvas* canvas,
+                                const views::CullSet& cull_set) {
   // Paint the |infobar_container_| last so that it may paint its
   // overlapping tabs.
   for (int i = 0; i < child_count(); ++i) {
     View* child = child_at(i);
     if (child != infobar_container_ && !child->layer())
-      child->Paint(canvas);
+      child->Paint(canvas, cull_set);
   }
 
-  infobar_container_->Paint(canvas);
+  infobar_container_->Paint(canvas, cull_set);
 }
 
 void BrowserView::ViewHierarchyChanged(
diff --git a/chrome/browser/ui/views/frame/browser_view.h b/chrome/browser/ui/views/frame/browser_view.h
index 6a88847..3345b03 100644
--- a/chrome/browser/ui/views/frame/browser_view.h
+++ b/chrome/browser/ui/views/frame/browser_view.h
@@ -441,7 +441,8 @@ class BrowserView : public BrowserWindow,
   // Overridden from views::View:
   virtual const char* GetClassName() const OVERRIDE;
   virtual void Layout() OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
   virtual void ViewHierarchyChanged(
       const ViewHierarchyChangedDetails& details) OVERRIDE;
   virtual void ChildPreferredSizeChanged(View* child) OVERRIDE;
diff --git a/chrome/browser/ui/views/frame/top_container_view.cc b/chrome/browser/ui/views/frame/top_container_view.cc
index 1fa6e9a..e36d608 100644
--- a/chrome/browser/ui/views/frame/top_container_view.cc
+++ b/chrome/browser/ui/views/frame/top_container_view.cc
@@ -25,6 +25,6 @@ void TopContainerView::OnPaintBackground(gfx::Canvas* canvas) {
     // window controls) being painted underneath them. Clip rect has already
     // been set to the bounds of this view, so just paint the frame.
     views::View* frame = browser_view_->frame()->GetFrameView();
-    frame->Paint(canvas);
+    frame->Paint(canvas, views::CullSet());
   }
 }
diff --git a/chrome/browser/ui/views/infobars/infobar_view.cc b/chrome/browser/ui/views/infobars/infobar_view.cc
index 5f65f66..bd70505 100644
--- a/chrome/browser/ui/views/infobars/infobar_view.cc
+++ b/chrome/browser/ui/views/infobars/infobar_view.cc
@@ -278,7 +278,8 @@ void InfoBarView::ViewHierarchyChanged(
   SetBarTargetHeight(height);
 }
 
-void InfoBarView::PaintChildren(gfx::Canvas* canvas) {
+void InfoBarView::PaintChildren(gfx::Canvas* canvas,
+                                const views::CullSet& cull_set) {
   canvas->Save();
 
   // TODO(scr): This really should be the |fill_path_|, but the clipPath seems
@@ -289,7 +290,7 @@ void InfoBarView::PaintChildren(gfx::Canvas* canvas) {
   DCHECK_EQ(total_height(), height())
       << "Infobar piecewise heights do not match overall height";
   canvas->ClipRect(gfx::Rect(0, arrow_height(), width(), bar_height()));
-  views::View::PaintChildren(canvas);
+  views::View::PaintChildren(canvas, cull_set);
   canvas->Restore();
 }
 
diff --git a/chrome/browser/ui/views/infobars/infobar_view.h b/chrome/browser/ui/views/infobars/infobar_view.h
index 40fb70b..56d8bd7 100644
--- a/chrome/browser/ui/views/infobars/infobar_view.h
+++ b/chrome/browser/ui/views/infobars/infobar_view.h
@@ -122,7 +122,8 @@ class InfoBarView : public infobars::InfoBar,
   // views::View:
   virtual void GetAccessibleState(ui::AXViewState* state) OVERRIDE;
   virtual gfx::Size GetPreferredSize() OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
 
   // views::ExternalFocusTracker:
   virtual void OnWillChangeFocus(View* focused_before,
diff --git a/chrome/browser/ui/views/location_bar/location_bar_view.cc b/chrome/browser/ui/views/location_bar/location_bar_view.cc
index 4da181d..8b679a0 100644
--- a/chrome/browser/ui/views/location_bar/location_bar_view.cc
+++ b/chrome/browser/ui/views/location_bar/location_bar_view.cc
@@ -1433,14 +1433,15 @@ void LocationBarView::OnPaint(gfx::Canvas* canvas) {
   // inner shadow which should be drawn over the contents.
 }
 
-void LocationBarView::PaintChildren(gfx::Canvas* canvas) {
+void LocationBarView::PaintChildren(gfx::Canvas* canvas,
+                                    const views::CullSet& cull_set) {
   // Paint all the children except for the origin chip and the search button,
   // which will be painted after the border.
   for (int i = 0, count = child_count(); i < count; ++i) {
     if (!child_at(i)->layer() &&
         (child_at(i) != origin_chip_view_) &&
         (child_at(i) != search_button_))
-      child_at(i)->Paint(canvas);
+      child_at(i)->Paint(canvas, cull_set);
   }
 
   // For non-InstantExtendedAPI cases, if necessary, show focus rect. As we need
@@ -1459,8 +1460,8 @@ void LocationBarView::PaintChildren(gfx::Canvas* canvas) {
 
   // The origin chip and the search button must be painted after the border so
   // that the border shadow is not drawn over them.
-  origin_chip_view_->Paint(canvas);
-  search_button_->Paint(canvas);
+  origin_chip_view_->Paint(canvas, cull_set);
+  search_button_->Paint(canvas, cull_set);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
diff --git a/chrome/browser/ui/views/location_bar/location_bar_view.h b/chrome/browser/ui/views/location_bar/location_bar_view.h
index 752a9b7..0a034f3 100644
--- a/chrome/browser/ui/views/location_bar/location_bar_view.h
+++ b/chrome/browser/ui/views/location_bar/location_bar_view.h
@@ -370,7 +370,8 @@ class LocationBarView : public LocationBar,
   virtual const char* GetClassName() const OVERRIDE;
   virtual void OnBoundsChanged(const gfx::Rect& previous_bounds) OVERRIDE;
   virtual void OnPaint(gfx::Canvas* canvas) OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
 
   // views::ButtonListener:
   virtual void ButtonPressed(views::Button* sender,
diff --git a/chrome/browser/ui/views/location_bar/page_action_image_view.cc b/chrome/browser/ui/views/location_bar/page_action_image_view.cc
index 793866d..6302fb4 100644
--- a/chrome/browser/ui/views/location_bar/page_action_image_view.cc
+++ b/chrome/browser/ui/views/location_bar/page_action_image_view.cc
@@ -227,8 +227,9 @@ void PageActionImageView::OnIconUpdated() {
     UpdateVisibility(web_contents, current_url_);
 }
 
-void PageActionImageView::PaintChildren(gfx::Canvas* canvas) {
-  View::PaintChildren(canvas);
+void PageActionImageView::PaintChildren(gfx::Canvas* canvas,
+                                        const views::CullSet& cull_set) {
+  View::PaintChildren(canvas, cull_set);
   if (current_tab_id_ >= 0)
     page_action_->PaintBadge(canvas, GetLocalBounds(), current_tab_id_);
 }
diff --git a/chrome/browser/ui/views/location_bar/page_action_image_view.h b/chrome/browser/ui/views/location_bar/page_action_image_view.h
index 0d39ea1..89348a2 100644
--- a/chrome/browser/ui/views/location_bar/page_action_image_view.h
+++ b/chrome/browser/ui/views/location_bar/page_action_image_view.h
@@ -82,7 +82,8 @@ class PageActionImageView : public views::ImageView,
 
  private:
   // Overridden from View.
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
 
   // Shows the popup, with the given URL.
   void ShowPopupWithURL(const GURL& popup_url,
diff --git a/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.cc b/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.cc
index 7d1af39..197064b 100644
--- a/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.cc
+++ b/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.cc
@@ -370,7 +370,7 @@ void OmniboxPopupContentsView::OnGestureEvent(ui::GestureEvent* event) {
 void OmniboxPopupContentsView::PaintResultViews(gfx::Canvas* canvas) {
   canvas->DrawColor(result_view_at(0)->GetColor(
       OmniboxResultView::NORMAL, OmniboxResultView::BACKGROUND));
-  View::PaintChildren(canvas);
+  View::PaintChildren(canvas, views::CullSet());
 }
 
 int OmniboxPopupContentsView::CalculatePopupHeight() {
@@ -433,7 +433,8 @@ void OmniboxPopupContentsView::OnPaint(gfx::Canvas* canvas) {
                        width(), bottom_shadow_->height());
 }
 
-void OmniboxPopupContentsView::PaintChildren(gfx::Canvas* canvas) {
+void OmniboxPopupContentsView::PaintChildren(gfx::Canvas* canvas,
+                                             const views::CullSet& cull_set) {
   // We paint our children inside OnPaint().
 }
 
diff --git a/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.h b/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.h
index e54b5b7..97c8273 100644
--- a/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.h
+++ b/chrome/browser/ui/views/omnibox/omnibox_popup_contents_view.h
@@ -96,7 +96,8 @@ class OmniboxPopupContentsView : public views::View,
   // in an un-conventional way inside OnPaint. We use a separate canvas to
   // paint the children. Hence we override this method to a no-op so that
   // the view hierarchy does not "accidentally" trigger this.
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
 
   scoped_ptr<OmniboxPopupModel> model_;
 
diff --git a/chrome/browser/ui/views/tabs/tab_strip.cc b/chrome/browser/ui/views/tabs/tab_strip.cc
index 169d128..1cd3f50 100644
--- a/chrome/browser/ui/views/tabs/tab_strip.cc
+++ b/chrome/browser/ui/views/tabs/tab_strip.cc
@@ -1139,7 +1139,8 @@ void TabStrip::Layout() {
   DoLayout();
 }
 
-void TabStrip::PaintChildren(gfx::Canvas* canvas) {
+void TabStrip::PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) {
   // The view order doesn't match the paint order (tabs_ contains the tab
   // ordering). Additionally we need to paint the tabs that are closing in
   // |tabs_closing_map_|.
@@ -1165,7 +1166,7 @@ void TabStrip::PaintChildren(gfx::Canvas* canvas) {
   if (inactive_tab_alpha < 255)
     canvas->SaveLayerAlpha(inactive_tab_alpha);
 
-  PaintClosingTabs(canvas, tab_count());
+  PaintClosingTabs(canvas, tab_count(), cull_set);
 
   for (int i = tab_count() - 1; i >= 0; --i) {
     Tab* tab = tab_at(i);
@@ -1182,7 +1183,7 @@ void TabStrip::PaintChildren(gfx::Canvas* canvas) {
     } else if (!tab->IsActive()) {
       if (!tab->IsSelected()) {
         if (!stacking)
-          tab->Paint(canvas);
+          tab->Paint(canvas, cull_set);
       } else {
         selected_tabs.push_back(tab);
       }
@@ -1190,19 +1191,19 @@ void TabStrip::PaintChildren(gfx::Canvas* canvas) {
       active_tab = tab;
       active_tab_index = i;
     }
-    PaintClosingTabs(canvas, i);
+    PaintClosingTabs(canvas, i, cull_set);
   }
 
   // Draw from the left and then the right if we're in touch mode.
   if (stacking && active_tab_index >= 0) {
     for (int i = 0; i < active_tab_index; ++i) {
       Tab* tab = tab_at(i);
-      tab->Paint(canvas);
+      tab->Paint(canvas, cull_set);
     }
 
     for (int i = tab_count() - 1; i > active_tab_index; --i) {
       Tab* tab = tab_at(i);
-      tab->Paint(canvas);
+      tab->Paint(canvas, cull_set);
     }
   }
   if (inactive_tab_alpha < 255)
@@ -1226,26 +1227,26 @@ void TabStrip::PaintChildren(gfx::Canvas* canvas) {
   // Now selected but not active. We don't want these dimmed if using native
   // frame, so they're painted after initial pass.
   for (size_t i = 0; i < selected_tabs.size(); ++i)
-    selected_tabs[i]->Paint(canvas);
+    selected_tabs[i]->Paint(canvas, cull_set);
 
   // Next comes the active tab.
   if (active_tab && !is_dragging)
-    active_tab->Paint(canvas);
+    active_tab->Paint(canvas, cull_set);
 
   // Paint the New Tab button.
   if (inactive_tab_alpha < 255)
     canvas->SaveLayerAlpha(inactive_tab_alpha);
-  newtab_button_->Paint(canvas);
+  newtab_button_->Paint(canvas, cull_set);
   if (inactive_tab_alpha < 255)
     canvas->Restore();
 
   // And the dragged tabs.
   for (size_t i = 0; i < tabs_dragging.size(); ++i)
-    tabs_dragging[i]->Paint(canvas);
+    tabs_dragging[i]->Paint(canvas, cull_set);
 
   // If the active tab is being dragged, it goes last.
   if (active_tab && is_dragging)
-    active_tab->Paint(canvas);
+    active_tab->Paint(canvas, cull_set);
 }
 
 const char* TabStrip::GetClassName() const {
@@ -1975,14 +1976,16 @@ TabDragController* TabStrip::ReleaseDragController() {
   return drag_controller_.release();
 }
 
-void TabStrip::PaintClosingTabs(gfx::Canvas* canvas, int index) {
+void TabStrip::PaintClosingTabs(gfx::Canvas* canvas,
+                                int index,
+                                const views::CullSet& cull_set) {
   if (tabs_closing_map_.find(index) == tabs_closing_map_.end())
     return;
 
   const std::vector<Tab*>& tabs = tabs_closing_map_[index];
   for (std::vector<Tab*>::const_reverse_iterator i(tabs.rbegin());
        i != tabs.rend(); ++i) {
-    (*i)->Paint(canvas);
+    (*i)->Paint(canvas, cull_set);
   }
 }
 
diff --git a/chrome/browser/ui/views/tabs/tab_strip.h b/chrome/browser/ui/views/tabs/tab_strip.h
index 0e717be..b0f47f1 100644
--- a/chrome/browser/ui/views/tabs/tab_strip.h
+++ b/chrome/browser/ui/views/tabs/tab_strip.h
@@ -214,7 +214,8 @@ class TabStrip : public views::View,
 
   // views::View overrides:
   virtual void Layout() OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
   virtual const char* GetClassName() const OVERRIDE;
   virtual gfx::Size GetPreferredSize() OVERRIDE;
   // NOTE: the drag and drop methods are invoked from FrameView. This is done
@@ -409,7 +410,9 @@ class TabStrip : public views::View,
   TabDragController* ReleaseDragController();
 
   // Paints all the tabs in |tabs_closing_map_[index]|.
-  void PaintClosingTabs(gfx::Canvas* canvas, int index);
+  void PaintClosingTabs(gfx::Canvas* canvas,
+                        int index,
+                        const views::CullSet& cull_set);
 
   // Invoked when a mouse event occurs over |source|. Potentially switches the
   // layout type.
diff --git a/chrome/browser/ui/views/toolbar/browser_action_view.cc b/chrome/browser/ui/views/toolbar/browser_action_view.cc
index f45634f..7cb342c 100644
--- a/chrome/browser/ui/views/toolbar/browser_action_view.cc
+++ b/chrome/browser/ui/views/toolbar/browser_action_view.cc
@@ -81,8 +81,9 @@ gfx::Size BrowserActionView::GetPreferredSize() {
                    BrowserActionsContainer::IconHeight());
 }
 
-void BrowserActionView::PaintChildren(gfx::Canvas* canvas) {
-  View::PaintChildren(canvas);
+void BrowserActionView::PaintChildren(gfx::Canvas* canvas,
+                                      const views::CullSet& cull_set) {
+  View::PaintChildren(canvas, cull_set);
   ExtensionAction* action = button()->browser_action();
   int tab_id = delegate_->GetCurrentTabId();
   if (tab_id >= 0)
diff --git a/chrome/browser/ui/views/toolbar/browser_action_view.h b/chrome/browser/ui/views/toolbar/browser_action_view.h
index eb5aa87..1ac3683 100644
--- a/chrome/browser/ui/views/toolbar/browser_action_view.h
+++ b/chrome/browser/ui/views/toolbar/browser_action_view.h
@@ -78,7 +78,8 @@ class BrowserActionView : public views::View {
 
  protected:
   // Overridden from views::View to paint the badge on top of children.
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
 
  private:
   // The Browser object this view is associated with.
diff --git a/ui/app_list/views/app_list_view.cc b/ui/app_list/views/app_list_view.cc
index 0499d45..0c5c5f70 100644
--- a/ui/app_list/views/app_list_view.cc
+++ b/ui/app_list/views/app_list_view.cc
@@ -204,8 +204,8 @@ gfx::Size AppListView::GetPreferredSize() {
   return app_list_main_view_->GetPreferredSize();
 }
 
-void AppListView::Paint(gfx::Canvas* canvas) {
-  views::BubbleDelegateView::Paint(canvas);
+void AppListView::Paint(gfx::Canvas* canvas, const views::CullSet& cull_set) {
+  views::BubbleDelegateView::Paint(canvas, cull_set);
   if (g_next_paint_callback) {
     g_next_paint_callback();
     g_next_paint_callback = NULL;
diff --git a/ui/app_list/views/app_list_view.h b/ui/app_list/views/app_list_view.h
index 7180918..83ac2d6 100644
--- a/ui/app_list/views/app_list_view.h
+++ b/ui/app_list/views/app_list_view.h
@@ -80,7 +80,8 @@ class APP_LIST_EXPORT AppListView : public views::BubbleDelegateView,
 
   // Overridden from views::View:
   virtual gfx::Size GetPreferredSize() OVERRIDE;
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE;
+  virtual void Paint(gfx::Canvas* canvas,
+                     const views::CullSet& cull_set) OVERRIDE;
   virtual void OnThemeChanged() OVERRIDE;
 
   // WidgetDelegate overrides:
diff --git a/ui/app_list/views/speech_view.cc b/ui/app_list/views/speech_view.cc
index 0f3a499..eaa1094 100644
--- a/ui/app_list/views/speech_view.cc
+++ b/ui/app_list/views/speech_view.cc
@@ -52,7 +52,8 @@ class SoundLevelIndicator : public views::View {
 
  private:
   // Overridden from views::View:
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE;
+  virtual void Paint(gfx::Canvas* canvas,
+                     const views::CullSet& cull_set) OVERRIDE;
 
   DISALLOW_COPY_AND_ASSIGN(SoundLevelIndicator);
 };
@@ -61,7 +62,8 @@ SoundLevelIndicator::SoundLevelIndicator() {}
 
 SoundLevelIndicator::~SoundLevelIndicator() {}
 
-void SoundLevelIndicator::Paint(gfx::Canvas* canvas) {
+void SoundLevelIndicator::Paint(gfx::Canvas* canvas,
+                                const views::CullSet& cull_set) {
   SkPaint paint;
   paint.setStyle(SkPaint::kFill_Style);
   paint.setColor(kSoundLevelIndicatorColor);
diff --git a/ui/message_center/views/bounded_label.cc b/ui/message_center/views/bounded_label.cc
index 8d43f41..1b2412a 100644
--- a/ui/message_center/views/bounded_label.cc
+++ b/ui/message_center/views/bounded_label.cc
@@ -335,9 +335,9 @@ int BoundedLabel::GetHeightForWidth(int width) {
          label_->GetSizeForWidthAndLines(width, line_limit_).height() : 0;
 }
 
-void BoundedLabel::Paint(gfx::Canvas* canvas) {
+void BoundedLabel::Paint(gfx::Canvas* canvas, const views::CullSet& cull_set) {
   if (visible())
-    label_->Paint(canvas);
+    label_->Paint(canvas, cull_set);
 }
 
 bool BoundedLabel::HitTestRect(const gfx::Rect& rect) const {
diff --git a/ui/message_center/views/bounded_label.h b/ui/message_center/views/bounded_label.h
index 9f13949..2fa04d7 100644
--- a/ui/message_center/views/bounded_label.h
+++ b/ui/message_center/views/bounded_label.h
@@ -53,7 +53,8 @@ class MESSAGE_CENTER_EXPORT BoundedLabel : public views::View {
   virtual int GetBaseline() const OVERRIDE;
   virtual gfx::Size GetPreferredSize() OVERRIDE;
   virtual int GetHeightForWidth(int width) OVERRIDE;
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE;
+  virtual void Paint(gfx::Canvas* canvas,
+                     const views::CullSet& cull_set) OVERRIDE;
   virtual bool HitTestRect(const gfx::Rect& rect) const OVERRIDE;
   virtual void GetAccessibleState(ui::AXViewState* state) OVERRIDE;
 
diff --git a/ui/message_center/views/message_center_view.cc b/ui/message_center/views/message_center_view.cc
index 599b71d..aadbf83 100644
--- a/ui/message_center/views/message_center_view.cc
+++ b/ui/message_center/views/message_center_view.cc
@@ -123,7 +123,8 @@ class MessageListView : public views::View,
   virtual void Layout() OVERRIDE;
   virtual gfx::Size GetPreferredSize() OVERRIDE;
   virtual int GetHeightForWidth(int width) OVERRIDE;
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_set) OVERRIDE;
   virtual void ReorderChildLayers(ui::Layer* parent_layer) OVERRIDE;
 
   // Overridden from views::BoundsAnimatorObserver.
@@ -305,12 +306,13 @@ int MessageListView::GetHeightForWidth(int width) {
   return height + GetInsets().height();
 }
 
-void MessageListView::PaintChildren(gfx::Canvas* canvas) {
+void MessageListView::PaintChildren(gfx::Canvas* canvas,
+                                    const views::CullSet& cull_set) {
   // Paint in the inversed order. Otherwise upper notification may be
   // hidden by the lower one.
   for (int i = child_count() - 1; i >= 0; --i) {
     if (!child_at(i)->layer())
-      child_at(i)->Paint(canvas);
+      child_at(i)->Paint(canvas, cull_set);
   }
 }
 
diff --git a/ui/views/controls/menu/submenu_view.cc b/ui/views/controls/menu/submenu_view.cc
index 2b59507..a79f076 100644
--- a/ui/views/controls/menu/submenu_view.cc
+++ b/ui/views/controls/menu/submenu_view.cc
@@ -177,8 +177,9 @@ ui::TextInputClient* SubmenuView::GetTextInputClient() {
   return &prefix_selector_;
 }
 
-void SubmenuView::PaintChildren(gfx::Canvas* canvas) {
-  View::PaintChildren(canvas);
+void SubmenuView::PaintChildren(gfx::Canvas* canvas,
+                                const views::CullSet& cull_set) {
+  View::PaintChildren(canvas, cull_set);
 
   if (drop_item_ && drop_position_ != MenuDelegate::DROP_ON)
     PaintDropIndicator(canvas, drop_item_, drop_position_);
diff --git a/ui/views/controls/menu/submenu_view.h b/ui/views/controls/menu/submenu_view.h
index 429581c..6cfefad 100644
--- a/ui/views/controls/menu/submenu_view.h
+++ b/ui/views/controls/menu/submenu_view.h
@@ -62,7 +62,8 @@ class VIEWS_EXPORT SubmenuView : public PrefixDelegate,
   virtual ui::TextInputClient* GetTextInputClient() OVERRIDE;
 
   // Painting.
-  virtual void PaintChildren(gfx::Canvas* canvas) OVERRIDE;
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const views::CullSet& cull_view) OVERRIDE;
 
   // Drag and drop methods. These are forwarded to the MenuController.
   virtual bool GetDropFormats(
diff --git a/ui/views/controls/separator.cc b/ui/views/controls/separator.cc
index cbf16de..0dc7f21 100644
--- a/ui/views/controls/separator.cc
+++ b/ui/views/controls/separator.cc
@@ -38,7 +38,7 @@ void Separator::GetAccessibleState(ui::AXViewState* state) {
   state->role = ui::AX_ROLE_SPLITTER;
 }
 
-void Separator::Paint(gfx::Canvas* canvas) {
+void Separator::Paint(gfx::Canvas* canvas, const views::CullSet& cull_set) {
   canvas->FillRect(bounds(), kDefaultColor);
 }
 
diff --git a/ui/views/controls/separator.h b/ui/views/controls/separator.h
index 7dfe0e6..86e619a 100644
--- a/ui/views/controls/separator.h
+++ b/ui/views/controls/separator.h
@@ -30,7 +30,8 @@ class VIEWS_EXPORT Separator : public View {
   // Overridden from View:
   virtual gfx::Size GetPreferredSize() OVERRIDE;
   virtual void GetAccessibleState(ui::AXViewState* state) OVERRIDE;
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE;
+  virtual void Paint(gfx::Canvas* canvas,
+                     const views::CullSet& cull_set) OVERRIDE;
   virtual const char* GetClassName() const OVERRIDE;
 
  private:
diff --git a/ui/views/controls/textfield/textfield.cc b/ui/views/controls/textfield/textfield.cc
index 6d513a1..78d5ae5 100644
--- a/ui/views/controls/textfield/textfield.cc
+++ b/ui/views/controls/textfield/textfield.cc
@@ -955,7 +955,7 @@ void Textfield::WriteDragDataForView(View* sender,
   // Desktop Linux Aura does not yet support transparency in drag images.
   canvas->DrawColor(background);
 #endif
-  label.Paint(canvas.get());
+  label.Paint(canvas.get(), views::CullSet());
   const gfx::Vector2d kOffset(-15, 0);
   drag_utils::SetDragImageOnDataObject(*canvas, label.size(), kOffset, data);
   if (controller_)
diff --git a/ui/views/cull_set.cc b/ui/views/cull_set.cc
new file mode 100644
index 0000000..65566e0
--- /dev/null
+++ b/ui/views/cull_set.cc
@@ -0,0 +1,26 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "ui/views/cull_set.h"
+
+namespace views {
+
+CullSet::CullSet() {
+}
+
+CullSet::~CullSet() {
+}
+
+CullSet::CullSet(scoped_ptr<base::hash_set<intptr_t> > cull_set)
+    : cull_set_(cull_set.Pass()) {
+}
+
+bool CullSet::ShouldPaint(const View* view) const {
+  if (cull_set_)
+    return (cull_set_->count(reinterpret_cast<intptr_t>(view)) > 0);
+
+  return true;
+}
+
+}  // namespace views
diff --git a/ui/views/cull_set.h b/ui/views/cull_set.h
new file mode 100644
index 0000000..03f7cff
--- /dev/null
+++ b/ui/views/cull_set.h
@@ -0,0 +1,47 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef UI_VIEWS_CULL_SET_H_
+#define UI_VIEWS_CULL_SET_H_
+
+#include "base/containers/hash_tables.h"
+#include "base/macros.h"
+#include "base/memory/scoped_ptr.h"
+#include "ui/views/views_export.h"
+
+namespace views {
+
+class View;
+
+// A CullSet defines a set of View pointers which have been possibly culled
+// from painting or other bounds-checking operations. It wraps a set of
+// pointers to views, or NULL if no such set is available.
+class VIEWS_EXPORT CullSet {
+ public:
+  // Default constructor builds a CullSet that will always return true for
+  // ShouldPaint().
+  CullSet();
+  ~CullSet();
+
+  // Wraps a set of pointers to Views, as might be provided by
+  // gfx::RTree::Query(), that intersect the damage rect and therefore need
+  // to be painted. CullSet takes ownership of the provided pointer.
+  CullSet(scoped_ptr<base::hash_set<intptr_t> > cull_set);
+
+  // Returns true if |view| needs to be painted.
+  bool ShouldPaint(const View* view) const;
+
+ private:
+  friend class BoundsTreeTestView;
+
+  // The set of Views that collided with the query rectangle provided to the
+  // RTree data structure, or NULL if one is not available.
+  scoped_ptr<base::hash_set<intptr_t> > cull_set_;
+
+  DISALLOW_COPY_AND_ASSIGN(CullSet);
+};
+
+}  // namespace views
+
+#endif  // UI_VIEWS_CULL_SET_H_
diff --git a/ui/views/view.cc b/ui/views/view.cc
index bbd1240..5980706 100644
--- a/ui/views/view.cc
+++ b/ui/views/view.cc
@@ -158,6 +158,7 @@ View::View()
       enabled_(true),
       notify_enter_exit_on_child_(false),
       registered_for_visible_bounds_notification_(false),
+      root_bounds_dirty_(true),
       clip_insets_(0, 0, 0, 0),
       needs_layout_(true),
       flip_canvas_on_paint_for_rtl_ui_(false),
@@ -234,6 +235,9 @@ void View::AddChildViewAt(View* view, int index) {
   view->parent_ = this;
   children_.insert(children_.begin() + index, view);
 
+  // Instruct the view to recompute its root bounds on next Paint().
+  view->SetRootBoundsDirty(true);
+
   views::Widget* widget = GetWidget();
   if (widget) {
     const ui::NativeTheme* new_theme = view->GetNativeTheme();
@@ -512,6 +516,31 @@ void View::SetTransform(const gfx::Transform& transform) {
 }
 
 void View::SetPaintToLayer(bool paint_to_layer) {
+  if (paint_to_layer_ == paint_to_layer)
+    return;
+
+  // If this is a change in state we will also need to update bounds trees.
+  if (paint_to_layer) {
+    // Gaining a layer means becoming a paint root. We must remove ourselves
+    // from our old paint root, if we had one. Traverse up view tree to find old
+    // paint root.
+    View* old_paint_root = parent_;
+    while (old_paint_root && !old_paint_root->IsPaintRoot())
+      old_paint_root = old_paint_root->parent_;
+
+    // Remove our and our children's bounds from the old tree. This will also
+    // mark all of our bounds as dirty.
+    if (old_paint_root && old_paint_root->bounds_tree_)
+      RemoveRootBounds(old_paint_root->bounds_tree_.get());
+
+  } else {
+    // Losing a layer means we are no longer a paint root, so delete our
+    // bounds tree and mark ourselves as dirty for future insertion into our
+    // new paint root's bounds tree.
+    bounds_tree_.reset();
+    SetRootBoundsDirty(true);
+  }
+
   paint_to_layer_ = paint_to_layer;
   if (paint_to_layer_ && !layer()) {
     CreateLayer();
@@ -772,32 +801,65 @@ void View::SchedulePaintInRect(const gfx::Rect& rect) {
   }
 }
 
-void View::Paint(gfx::Canvas* canvas) {
-  TRACE_EVENT1("views", "View::Paint", "class", GetClassName());
+void View::Paint(gfx::Canvas* canvas, const CullSet& cull_set) {
+  // The cull_set may allow us to skip painting without canvas construction or
+  // even canvas rect intersection.
+  if (cull_set.ShouldPaint(this)) {
+    TRACE_EVENT1("views", "View::Paint", "class", GetClassName());
 
-  gfx::ScopedCanvas scoped_canvas(canvas);
+    gfx::ScopedCanvas scoped_canvas(canvas);
 
-  // Paint this View and its children, setting the clip rect to the bounds
-  // of this View and translating the origin to the local bounds' top left
-  // point.
-  //
-  // Note that the X (or left) position we pass to ClipRectInt takes into
-  // consideration whether or not the view uses a right-to-left layout so that
-  // we paint our view in its mirrored position if need be.
-  gfx::Rect clip_rect = bounds();
-  clip_rect.Inset(clip_insets_);
-  if (parent_)
-    clip_rect.set_x(parent_->GetMirroredXForRect(clip_rect));
-  canvas->ClipRect(clip_rect);
-  if (canvas->IsClipEmpty())
-    return;
+    // Paint this View and its children, setting the clip rect to the bounds
+    // of this View and translating the origin to the local bounds' top left
+    // point.
+    //
+    // Note that the X (or left) position we pass to ClipRectInt takes into
+    // consideration whether or not the view uses a right-to-left layout so that
+    // we paint our view in its mirrored position if need be.
+    gfx::Rect clip_rect = bounds();
+    clip_rect.Inset(clip_insets_);
+    if (parent_)
+      clip_rect.set_x(parent_->GetMirroredXForRect(clip_rect));
+    canvas->ClipRect(clip_rect);
+    if (canvas->IsClipEmpty())
+      return;
+
+    // Non-empty clip, translate the graphics such that 0,0 corresponds to where
+    // this view is located (related to its parent).
+    canvas->Translate(GetMirroredPosition().OffsetFromOrigin());
+    canvas->Transform(GetTransform());
 
-  // Non-empty clip, translate the graphics such that 0,0 corresponds to
-  // where this view is located (related to its parent).
-  canvas->Translate(GetMirroredPosition().OffsetFromOrigin());
-  canvas->Transform(GetTransform());
+    // If we are a paint root, we need to construct our own CullSet object for
+    // propagation to our children.
+    if (IsPaintRoot()) {
+      if (!bounds_tree_)
+        bounds_tree_.reset(new gfx::RTree(2, 5));
 
-  PaintCommon(canvas);
+      // Recompute our bounds tree as needed.
+      UpdateRootBounds(bounds_tree_.get(), gfx::Vector2d());
+
+      // Grab the clip rect from the supplied canvas to use as the query rect.
+      gfx::Rect canvas_bounds;
+      if (!canvas->GetClipBounds(&canvas_bounds)) {
+        NOTREACHED() << "Failed to get clip bounds from the canvas!";
+        return;
+      }
+
+      // Now query our bounds_tree_ for a set of damaged views that intersect
+      // our canvas bounds.
+      scoped_ptr<base::hash_set<intptr_t> > damaged_views(
+          new base::hash_set<intptr_t>());
+      bounds_tree_->Query(canvas_bounds, damaged_views.get());
+      // Construct a CullSet to wrap the damaged views set, it will delete it
+      // for us on scope exit.
+      CullSet paint_root_cull_set(damaged_views.Pass());
+      // Paint all descendents using our new cull set.
+      PaintCommon(canvas, paint_root_cull_set);
+    } else {
+      // Not a paint root, so we can proceed as normal.
+      PaintCommon(canvas, cull_set);
+    }
+  }
 }
 
 void View::set_background(Background* b) {
@@ -1389,11 +1451,11 @@ void View::NativeViewHierarchyChanged() {
 
 // Painting --------------------------------------------------------------------
 
-void View::PaintChildren(gfx::Canvas* canvas) {
+void View::PaintChildren(gfx::Canvas* canvas, const CullSet& cull_set) {
   TRACE_EVENT1("views", "View::PaintChildren", "class", GetClassName());
   for (int i = 0, count = child_count(); i < count; ++i)
     if (!child_at(i)->layer())
-      child_at(i)->Paint(canvas);
+      child_at(i)->Paint(canvas, cull_set);
 }
 
 void View::OnPaint(gfx::Canvas* canvas) {
@@ -1420,6 +1482,10 @@ void View::OnPaintBorder(gfx::Canvas* canvas) {
   }
 }
 
+bool View::IsPaintRoot() {
+  return paint_to_layer_ || !parent_;
+}
+
 // Accelerated Painting --------------------------------------------------------
 
 void View::SetFillsBoundsOpaquely(bool fills_bounds_opaquely) {
@@ -1502,7 +1568,7 @@ void View::UpdateChildLayerBounds(const gfx::Vector2d& offset) {
 void View::OnPaintLayer(gfx::Canvas* canvas) {
   if (!layer() || !layer()->fills_bounds_opaquely())
     canvas->DrawColor(SK_ColorBLACK, SkXfermode::kClear_Mode);
-  PaintCommon(canvas);
+  PaintCommon(canvas, CullSet());
 }
 
 void View::OnDeviceScaleFactorChanged(float device_scale_factor) {
@@ -1750,7 +1816,6 @@ std::string View::DoPrintViewGraph(bool first, View* view_with_children) {
 
   return result;
 }
-
 #endif
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -1787,7 +1852,7 @@ void View::SchedulePaintBoundsChanged(SchedulePaintType type) {
   }
 }
 
-void View::PaintCommon(gfx::Canvas* canvas) {
+void View::PaintCommon(gfx::Canvas* canvas, const CullSet& cull_set) {
   if (!visible_)
     return;
 
@@ -1806,7 +1871,7 @@ void View::PaintCommon(gfx::Canvas* canvas) {
     OnPaint(canvas);
   }
 
-  PaintChildren(canvas);
+  PaintChildren(canvas, cull_set);
 }
 
 // Tree operations -------------------------------------------------------------
@@ -1837,6 +1902,13 @@ void View::DoRemoveChildView(View* view,
         view->SchedulePaint();
       GetWidget()->NotifyWillRemoveView(view);
     }
+
+    // Remove the bounds of this child and any of its descendants from our
+    // paint root bounds tree.
+    gfx::RTree* bounds_tree = GetBoundsTreeFromPaintRoot();
+    if (bounds_tree)
+      view->RemoveRootBounds(bounds_tree);
+
     view->PropagateRemoveNotifications(this, new_parent);
     view->parent_ = NULL;
     view->UpdateLayerVisibility();
@@ -1928,6 +2000,12 @@ void View::VisibilityChangedImpl(View* starting_from, bool is_visible) {
 }
 
 void View::BoundsChanged(const gfx::Rect& previous_bounds) {
+  // Mark our bounds as dirty for the paint root, also see if we need to
+  // recompute our children's bounds due to origin change.
+  bool origin_changed =
+      previous_bounds.OffsetFromOrigin() != bounds_.OffsetFromOrigin();
+  SetRootBoundsDirty(origin_changed);
+
   if (visible_) {
     // Paint the new bounds.
     SchedulePaintBoundsChanged(
@@ -2024,6 +2102,69 @@ void View::SetLayerBounds(const gfx::Rect& bounds) {
   layer()->SetBounds(bounds);
 }
 
+void View::SetRootBoundsDirty(bool origin_changed) {
+  root_bounds_dirty_ = true;
+
+  if (origin_changed) {
+    // Inform our children that their root bounds are dirty, as their relative
+    // coordinates in paint root space have changed since ours have changed.
+    for (Views::const_iterator i(children_.begin()); i != children_.end();
+         ++i) {
+      if (!(*i)->IsPaintRoot())
+        (*i)->SetRootBoundsDirty(origin_changed);
+    }
+  }
+}
+
+void View::UpdateRootBounds(gfx::RTree* tree, const gfx::Vector2d& offset) {
+  // No need to recompute bounds if we haven't flagged ours as dirty.
+  TRACE_EVENT1("views", "View::UpdateRootBounds", "class", GetClassName());
+
+  // Add our own offset to the provided offset, for our own bounds update and
+  // for propagation to our children if needed.
+  gfx::Vector2d view_offset = offset + bounds_.OffsetFromOrigin();
+
+  // If our bounds have changed we must re-insert our new bounds to the tree.
+  if (root_bounds_dirty_) {
+    root_bounds_dirty_ = false;
+    gfx::Rect bounds(
+        view_offset.x(), view_offset.y(), bounds_.width(), bounds_.height());
+    tree->Insert(bounds, reinterpret_cast<intptr_t>(this));
+  }
+
+  // Update our children's bounds if needed.
+  for (Views::const_iterator i(children_.begin()); i != children_.end(); ++i) {
+    // We don't descend in to layer views for bounds recomputation, as they
+    // manage their own RTree as paint roots.
+    if (!(*i)->IsPaintRoot())
+      (*i)->UpdateRootBounds(tree, view_offset);
+  }
+}
+
+void View::RemoveRootBounds(gfx::RTree* tree) {
+  tree->Remove(reinterpret_cast<intptr_t>(this));
+
+  root_bounds_dirty_ = true;
+
+  for (Views::const_iterator i(children_.begin()); i != children_.end(); ++i) {
+    if (!(*i)->IsPaintRoot())
+      (*i)->RemoveRootBounds(tree);
+  }
+}
+
+gfx::RTree* View::GetBoundsTreeFromPaintRoot() {
+  gfx::RTree* bounds_tree = bounds_tree_.get();
+  View* paint_root = this;
+  while (!bounds_tree && !paint_root->IsPaintRoot()) {
+    // Assumption is that if IsPaintRoot() is false then parent_ is valid.
+    DCHECK(paint_root);
+    paint_root = paint_root->parent_;
+    bounds_tree = paint_root->bounds_tree_.get();
+  }
+
+  return bounds_tree;
+}
+
 // Transformations -------------------------------------------------------------
 
 bool View::GetTransformRelativeTo(const View* ancestor,
diff --git a/ui/views/view.h b/ui/views/view.h
index 027e212..f26d8f0 100644
--- a/ui/views/view.h
+++ b/ui/views/view.h
@@ -27,10 +27,12 @@
 #include "ui/events/event.h"
 #include "ui/events/event_target.h"
 #include "ui/events/event_targeter.h"
+#include "ui/gfx/geometry/r_tree.h"
 #include "ui/gfx/insets.h"
 #include "ui/gfx/native_widget_types.h"
 #include "ui/gfx/rect.h"
 #include "ui/gfx/vector2d.h"
+#include "ui/views/cull_set.h"
 #include "ui/views/views_export.h"
 
 #if defined(OS_WIN)
@@ -502,7 +504,7 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   // for View coordinates and language direction as required, allows the View
   // to paint itself via the various OnPaint*() event handlers and then paints
   // the hierarchy beneath it.
-  virtual void Paint(gfx::Canvas* canvas);
+  virtual void Paint(gfx::Canvas* canvas, const CullSet& cull_set);
 
   // The background object is owned by this object and may be NULL.
   void set_background(Background* b);
@@ -1076,7 +1078,7 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
 
   // Responsible for calling Paint() on child Views. Override to control the
   // order child Views are painted.
-  virtual void PaintChildren(gfx::Canvas* canvas);
+  virtual void PaintChildren(gfx::Canvas* canvas, const CullSet& cull_set);
 
   // Override to provide rendering in any part of the View's bounds. Typically
   // this is the "contents" of the view. If you override this method you will
@@ -1091,6 +1093,11 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   // Override to paint a border not specified by SetBorder().
   virtual void OnPaintBorder(gfx::Canvas* canvas);
 
+  // Returns true if this View is the root for paint events, and should
+  // therefore maintain a |bounds_tree_| member and use it for paint damage rect
+  // calculations.
+  virtual bool IsPaintRoot();
+
   // Accelerated painting ------------------------------------------------------
 
   // Returns the offset from this view to the nearest ancestor with a layer. If
@@ -1251,7 +1258,7 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
 
   // Common Paint() code shared by accelerated and non-accelerated code paths to
   // invoke OnPaint() on the View.
-  void PaintCommon(gfx::Canvas* canvas);
+  void PaintCommon(gfx::Canvas* canvas, const CullSet& cull_set);
 
   // Tree operations -----------------------------------------------------------
 
@@ -1320,6 +1327,25 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   // Sets the layer's bounds given in DIP coordinates.
   void SetLayerBounds(const gfx::Rect& bounds_in_dip);
 
+  // Sets the bit indicating that the cached bounds for this object within the
+  // root view bounds tree are no longer valid. If |origin_changed| is true sets
+  // the same bit for all of our children as well.
+  void SetRootBoundsDirty(bool origin_changed);
+
+  // If needed, updates the bounds rectangle in paint root coordinate space
+  // in the supplied RTree. Recurses to children for recomputation as well.
+  void UpdateRootBounds(gfx::RTree* bounds_tree, const gfx::Vector2d& offset);
+
+  // Remove self and all children from the supplied bounds tree. This is used,
+  // for example, when a view gets a layer and therefore becomes paint root. It
+  // needs to remove all references to itself and its children from any previous
+  // paint root that may have been tracking it.
+  void RemoveRootBounds(gfx::RTree* bounds_tree);
+
+  // Traverse up the View hierarchy to the first ancestor that is a paint root
+  // and return a pointer to its |bounds_tree_| or NULL if no tree is found.
+  gfx::RTree* GetBoundsTreeFromPaintRoot();
+
   // Transformations -----------------------------------------------------------
 
   // Returns in |transform| the transform to get from coordinates of |ancestor|
@@ -1492,6 +1518,15 @@ class VIEWS_EXPORT View : public ui::LayerDelegate,
   // List of descendants wanting notification when their visible bounds change.
   scoped_ptr<Views> descendants_to_notify_;
 
+  // True if the bounds on this object have changed since the last time the
+  // paint root view constructed the spatial database.
+  bool root_bounds_dirty_;
+
+  // If this View IsPaintRoot() then this will be a pointer to a spatial data
+  // structure where we will keep the bounding boxes of all our children, for
+  // efficient paint damage rectangle intersection.
+  scoped_ptr<gfx::RTree> bounds_tree_;
+
   // Transformations -----------------------------------------------------------
 
   // Clipping parameters. skia transformation matrix does not give us clipping.
diff --git a/ui/views/view_unittest.cc b/ui/views/view_unittest.cc
index b1bcb6a..3685673 100644
--- a/ui/views/view_unittest.cc
+++ b/ui/views/view_unittest.cc
@@ -240,7 +240,7 @@ class TestView : public View {
   // Ignores GestureEvent by default.
   virtual void OnGestureEvent(ui::GestureEvent* event) OVERRIDE;
 
-  virtual void Paint(gfx::Canvas* canvas) OVERRIDE;
+  virtual void Paint(gfx::Canvas* canvas, const CullSet& cull_set) OVERRIDE;
   virtual void SchedulePaintInRect(const gfx::Rect& rect) OVERRIDE;
   virtual bool AcceleratorPressed(const ui::Accelerator& accelerator) OVERRIDE;
 
@@ -670,7 +670,7 @@ TEST_F(ViewTest, ScrollGestureEvent) {
 // Painting
 ////////////////////////////////////////////////////////////////////////////////
 
-void TestView::Paint(gfx::Canvas* canvas) {
+void TestView::Paint(gfx::Canvas* canvas, const CullSet& cull_set) {
   canvas->sk_canvas()->getClipBounds(&last_clip_);
 }
 
@@ -3463,6 +3463,246 @@ TEST_F(ViewLayerTest, RecreateLayerMovesNonViewChildren) {
   EXPECT_EQ(v.layer()->children()[1], child.layer());
 }
 
+class BoundsTreeTestView : public View {
+ public:
+  BoundsTreeTestView() {}
+
+  virtual void PaintChildren(gfx::Canvas* canvas,
+                             const CullSet& cull_set) OVERRIDE {
+    // Save out a copy of the cull_set before calling the base implementation.
+    last_cull_set_.clear();
+    if (cull_set.cull_set_) {
+      for (base::hash_set<intptr_t>::iterator it = cull_set.cull_set_->begin();
+           it != cull_set.cull_set_->end();
+           ++it) {
+        last_cull_set_.insert(reinterpret_cast<View*>(*it));
+      }
+    }
+    View::PaintChildren(canvas, cull_set);
+  }
+
+  std::set<View*> last_cull_set_;
+};
+
+TEST_F(ViewLayerTest, BoundsTreePaintUpdatesCullSet) {
+  BoundsTreeTestView* test_view = new BoundsTreeTestView;
+  widget()->SetContentsView(test_view);
+
+  View* v1 = new View();
+  v1->SetBoundsRect(gfx::Rect(10, 15, 150, 151));
+  test_view->AddChildView(v1);
+
+  View* v2 = new View();
+  v2->SetBoundsRect(gfx::Rect(20, 33, 40, 50));
+  v1->AddChildView(v2);
+
+  // Schedule a full-view paint to get everyone's rectangles updated.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Now we have test_view - v1 - v2. Damage to only test_view should only
+  // return root_view and test_view.
+  test_view->SchedulePaintInRect(gfx::Rect(0, 0, 1, 1));
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  EXPECT_EQ(2U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+
+  // Damage to v1 only should only return root_view, test_view, and v1.
+  test_view->SchedulePaintInRect(gfx::Rect(11, 16, 1, 1));
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  EXPECT_EQ(3U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v1));
+
+  // A Damage rect inside v2 should get all 3 views back in the |last_cull_set_|
+  // on call to TestView::Paint(), along with the widget root view.
+  test_view->SchedulePaintInRect(gfx::Rect(31, 49, 1, 1));
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  EXPECT_EQ(4U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v1));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v2));
+}
+
+TEST_F(ViewLayerTest, BoundsTreeSetBoundsChangesCullSet) {
+  BoundsTreeTestView* test_view = new BoundsTreeTestView;
+  widget()->SetContentsView(test_view);
+
+  View* v1 = new View;
+  v1->SetBoundsRect(gfx::Rect(5, 6, 100, 101));
+  test_view->AddChildView(v1);
+
+  View* v2 = new View;
+  v2->SetBoundsRect(gfx::Rect(20, 33, 40, 50));
+  v1->AddChildView(v2);
+
+  // Schedule a full-view paint to get everyone's rectangles updated.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Move v1 to a new origin out of the way of our next query.
+  v1->SetBoundsRect(gfx::Rect(50, 60, 100, 101));
+  // The move will force a repaint.
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Schedule a paint with damage rect where v1 used to be.
+  test_view->SchedulePaintInRect(gfx::Rect(5, 6, 10, 11));
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Should only have picked up root_view and test_view.
+  EXPECT_EQ(2U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+}
+
+TEST_F(ViewLayerTest, BoundsTreeLayerChangeMakesNewTree) {
+  BoundsTreeTestView* test_view = new BoundsTreeTestView;
+  widget()->SetContentsView(test_view);
+
+  View* v1 = new View;
+  v1->SetBoundsRect(gfx::Rect(5, 10, 15, 20));
+  test_view->AddChildView(v1);
+
+  View* v2 = new View;
+  v2->SetBoundsRect(gfx::Rect(1, 2, 3, 4));
+  v1->AddChildView(v2);
+
+  // Schedule a full-view paint to get everyone's rectangles updated.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Set v1 to paint to its own layer, it should remove itself from the
+  // test_view heiarchy and no longer intersect with damage rects in that cull
+  // set.
+  v1->SetPaintToLayer(true);
+
+  // Schedule another full-view paint.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  // v1 and v2 should no longer be present in the test_view cull_set.
+  EXPECT_EQ(2U, test_view->last_cull_set_.size());
+  EXPECT_EQ(0U, test_view->last_cull_set_.count(v1));
+  EXPECT_EQ(0U, test_view->last_cull_set_.count(v2));
+
+  // Now set v1 back to not painting to a layer.
+  v1->SetPaintToLayer(false);
+  // Schedule another full-view paint.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  // We should be back to the full cull set including v1 and v2.
+  EXPECT_EQ(4U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v1));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v2));
+}
+
+TEST_F(ViewLayerTest, BoundsTreeRemoveChildRemovesBounds) {
+  BoundsTreeTestView* test_view = new BoundsTreeTestView;
+  widget()->SetContentsView(test_view);
+
+  View* v1 = new View;
+  v1->SetBoundsRect(gfx::Rect(5, 10, 15, 20));
+  test_view->AddChildView(v1);
+
+  View* v2 = new View;
+  v2->SetBoundsRect(gfx::Rect(1, 2, 3, 4));
+  v1->AddChildView(v2);
+
+  // Schedule a full-view paint to get everyone's rectangles updated.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Now remove v1 from the root view.
+  test_view->RemoveChildView(v1);
+
+  // Schedule another full-view paint.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  // v1 and v2 should no longer be present in the test_view cull_set.
+  EXPECT_EQ(2U, test_view->last_cull_set_.size());
+  EXPECT_EQ(0U, test_view->last_cull_set_.count(v1));
+  EXPECT_EQ(0U, test_view->last_cull_set_.count(v2));
+
+  // View v1 and v2 are no longer part of view hierarchy and therefore won't be
+  // deleted with that hierarchy.
+  delete v1;
+}
+
+TEST_F(ViewLayerTest, BoundsTreeMoveViewMovesBounds) {
+  BoundsTreeTestView* test_view = new BoundsTreeTestView;
+  widget()->SetContentsView(test_view);
+
+  // Build hierarchy v1 - v2 - v3.
+  View* v1 = new View;
+  v1->SetBoundsRect(gfx::Rect(20, 30, 150, 160));
+  test_view->AddChildView(v1);
+
+  View* v2 = new View;
+  v2->SetBoundsRect(gfx::Rect(5, 10, 40, 50));
+  v1->AddChildView(v2);
+
+  View* v3 = new View;
+  v3->SetBoundsRect(gfx::Rect(1, 2, 3, 4));
+  v2->AddChildView(v3);
+
+  // Schedule a full-view paint and ensure all views are present in the cull.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+  EXPECT_EQ(5U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v1));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v2));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v3));
+
+  // Build an unrelated view hierarchy and move v2 in to it.
+  scoped_ptr<Widget> test_widget(new Widget);
+  Widget::InitParams params = CreateParams(Widget::InitParams::TYPE_POPUP);
+  params.bounds = gfx::Rect(10, 10, 500, 500);
+  params.ownership = Widget::InitParams::WIDGET_OWNS_NATIVE_WIDGET;
+  test_widget->Init(params);
+  test_widget->Show();
+  BoundsTreeTestView* widget_view = new BoundsTreeTestView;
+  test_widget->SetContentsView(widget_view);
+  widget_view->AddChildView(v2);
+
+  // Now schedule full-view paints in both widgets.
+  test_view->SchedulePaintInRect(test_view->bounds());
+  widget_view->SchedulePaintInRect(widget_view->bounds());
+  GetRootLayer()->GetCompositor()->ScheduleDraw();
+  ui::DrawWaiterForTest::Wait(GetRootLayer()->GetCompositor());
+
+  // Only v1 should be present in the first cull set.
+  EXPECT_EQ(3U, test_view->last_cull_set_.size());
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(widget()->GetRootView()));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(test_view));
+  EXPECT_EQ(1U, test_view->last_cull_set_.count(v1));
+
+  // We should find v2 and v3 in the widget_view cull_set.
+  EXPECT_EQ(4U, widget_view->last_cull_set_.size());
+  EXPECT_EQ(1U, widget_view->last_cull_set_.count(test_widget->GetRootView()));
+  EXPECT_EQ(1U, widget_view->last_cull_set_.count(widget_view));
+  EXPECT_EQ(1U, widget_view->last_cull_set_.count(v2));
+  EXPECT_EQ(1U, widget_view->last_cull_set_.count(v3));
+}
+
 TEST_F(ViewTest, FocusableAssertions) {
   // View subclasses may change insets based on whether they are focusable,
   // which effects the preferred size. To avoid preferred size changing around
diff --git a/ui/views/views.gyp b/ui/views/views.gyp
index d7cb8b6..ee3e33f 100644
--- a/ui/views/views.gyp
+++ b/ui/views/views.gyp
@@ -244,6 +244,8 @@
         'corewm/tooltip_controller.h',
         'corewm/tooltip_win.cc',
         'corewm/tooltip_win.h',
+        'cull_set.cc',
+        'cull_set.h',
         'debug_utils.cc',
         'debug_utils.h',
         'drag_controller.h',
diff --git a/ui/views/widget/desktop_aura/desktop_window_tree_host_win.cc b/ui/views/widget/desktop_aura/desktop_window_tree_host_win.cc
index ece2500..1ecd996 100644
--- a/ui/views/widget/desktop_aura/desktop_window_tree_host_win.cc
+++ b/ui/views/widget/desktop_aura/desktop_window_tree_host_win.cc
@@ -656,7 +656,7 @@ void DesktopWindowTreeHostWin::ResetWindowControls() {
 }
 
 void DesktopWindowTreeHostWin::PaintLayeredWindow(gfx::Canvas* canvas) {
-  GetWidget()->GetRootView()->Paint(canvas);
+  GetWidget()->GetRootView()->Paint(canvas, views::CullSet());
 }
 
 gfx::NativeViewAccessible DesktopWindowTreeHostWin::GetNativeViewAccessible() {
diff --git a/ui/views/widget/widget.cc b/ui/views/widget/widget.cc
index ca10892..d773f1f 100644
--- a/ui/views/widget/widget.cc
+++ b/ui/views/widget/widget.cc
@@ -1158,7 +1158,7 @@ void Widget::OnNativeWidgetPaint(gfx::Canvas* canvas) {
   // On Linux Aura, we can get here during Init() because of the
   // SetInitialBounds call.
   if (native_widget_initialized_)
-    GetRootView()->Paint(canvas);
+    GetRootView()->Paint(canvas, CullSet());
 }
 
 int Widget::GetNonClientComponent(const gfx::Point& point) {