1// Copyright 2014 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 "chrome/browser/chromeos/ui/accessibility_focus_ring_controller.h" 6 7#include "ash/display/display_controller.h" 8#include "ash/shell.h" 9#include "base/logging.h" 10#include "chrome/browser/chromeos/ui/focus_ring_layer.h" 11#include "ui/gfx/screen.h" 12 13namespace chromeos { 14 15namespace { 16 17// The number of pixels the focus ring is outset from the object it outlines, 18// which also determines the border radius of the rounded corners. 19// TODO(dmazzoni): take display resolution into account. 20const int kAccessibilityFocusRingMargin = 7; 21 22// Time to transition between one location and the next. 23const int kTransitionTimeMilliseconds = 300; 24 25// A Region is an unordered collection of Rects that maintains its 26// bounding box. Used in the middle of an algorithm that groups 27// adjacent and overlapping rects. 28struct Region { 29 explicit Region(gfx::Rect initial_rect) { 30 bounds = initial_rect; 31 rects.push_back(initial_rect); 32 } 33 gfx::Rect bounds; 34 std::vector<gfx::Rect> rects; 35}; 36 37} // namespace 38 39// static 40AccessibilityFocusRingController* 41 AccessibilityFocusRingController::GetInstance() { 42 return Singleton<AccessibilityFocusRingController>::get(); 43} 44 45AccessibilityFocusRingController::AccessibilityFocusRingController() 46 : compositor_(NULL) { 47} 48 49AccessibilityFocusRingController::~AccessibilityFocusRingController() { 50} 51 52void AccessibilityFocusRingController::SetFocusRing( 53 const std::vector<gfx::Rect>& rects) { 54 rects_ = rects; 55 Update(); 56} 57 58void AccessibilityFocusRingController::Update() { 59 previous_rings_.swap(rings_); 60 rings_.clear(); 61 RectsToRings(rects_, &rings_); 62 layers_.resize(rings_.size()); 63 for (size_t i = 0; i < rings_.size(); ++i) { 64 if (!layers_[i]) 65 layers_[i].reset(new AccessibilityFocusRingLayer(this)); 66 67 if (i > 0) { 68 // Focus rings other than the first one don't animate. 69 layers_[i]->Set(rings_[i]); 70 continue; 71 } 72 73 gfx::Rect bounds = rings_[0].GetBounds(); 74 gfx::Display display = 75 gfx::Screen::GetNativeScreen()->GetDisplayMatching(bounds); 76 aura::Window* root_window = ash::Shell::GetInstance()->display_controller() 77 ->GetRootWindowForDisplayId(display.id()); 78 ui::Compositor* compositor = root_window->layer()->GetCompositor(); 79 if (!compositor || root_window != layers_[0]->root_window()) { 80 layers_[0]->Set(rings_[0]); 81 if (compositor_ && compositor_->HasAnimationObserver(this)) { 82 compositor_->RemoveAnimationObserver(this); 83 compositor_ = NULL; 84 } 85 continue; 86 } 87 88 focus_change_time_ = base::TimeTicks::Now(); 89 if (!compositor->HasAnimationObserver(this)) { 90 compositor_ = compositor; 91 compositor_->AddAnimationObserver(this); 92 } 93 } 94} 95 96void AccessibilityFocusRingController::RectsToRings( 97 const std::vector<gfx::Rect>& src_rects, 98 std::vector<AccessibilityFocusRing>* rings) const { 99 if (src_rects.empty()) 100 return; 101 102 // Give all of the rects a margin. 103 std::vector<gfx::Rect> rects; 104 rects.resize(src_rects.size()); 105 for (size_t i = 0; i < src_rects.size(); ++i) { 106 rects[i] = src_rects[i]; 107 rects[i].Inset(-GetMargin(), -GetMargin()); 108 } 109 110 // Split the rects into contiguous regions. 111 std::vector<Region> regions; 112 regions.push_back(Region(rects[0])); 113 for (size_t i = 1; i < rects.size(); ++i) { 114 bool found = false; 115 for (size_t j = 0; j < regions.size(); ++j) { 116 if (Intersects(rects[i], regions[j].bounds)) { 117 regions[j].rects.push_back(rects[i]); 118 regions[j].bounds.Union(rects[i]); 119 found = true; 120 } 121 } 122 if (!found) { 123 regions.push_back(Region(rects[i])); 124 } 125 } 126 127 // Keep merging regions that intersect. 128 // TODO(dmazzoni): reduce the worst-case complexity! This appears like 129 // it could be O(n^3), make sure it's not in practice. 130 bool merged; 131 do { 132 merged = false; 133 for (size_t i = 0; i < regions.size() - 1 && !merged; ++i) { 134 for (size_t j = i + 1; j < regions.size() && !merged; ++j) { 135 if (Intersects(regions[i].bounds, regions[j].bounds)) { 136 regions[i].rects.insert(regions[i].rects.end(), 137 regions[j].rects.begin(), 138 regions[j].rects.end()); 139 regions[i].bounds.Union(regions[j].bounds); 140 regions.erase(regions.begin() + j); 141 merged = true; 142 } 143 } 144 } 145 } while (merged); 146 147 for (size_t i = 0; i < regions.size(); ++i) { 148 std::sort(regions[i].rects.begin(), regions[i].rects.end()); 149 rings->push_back(RingFromSortedRects(regions[i].rects)); 150 } 151} 152 153int AccessibilityFocusRingController::GetMargin() const { 154 return kAccessibilityFocusRingMargin; 155} 156 157// Given a vector of rects that all overlap, already sorted from top to bottom 158// and left to right, split them into three shapes covering the top, middle, 159// and bottom of a "paragraph shape". 160// 161// Input: 162// 163// +---+---+ 164// | 1 | 2 | 165// +---------------------+---+---+ 166// | 3 | 167// +--------+---------------+----+ 168// | 4 | 5 | 169// +--------+---------------+--+ 170// | 6 | 171// +---------+-----------------+ 172// | 7 | 173// +---------+ 174// 175// Output: 176// 177// +-------+ 178// | Top | 179// +---------------------+-------+ 180// | | 181// | | 182// | Middle | 183// | | 184// | | 185// +---------+-------------------+ 186// | Bottom | 187// +---------+ 188// 189// When there's no clear "top" or "bottom" segment, split the overall rect 190// evenly so that some of the area still fits into the "top" and "bottom" 191// segments. 192void AccessibilityFocusRingController::SplitIntoParagraphShape( 193 const std::vector<gfx::Rect>& rects, 194 gfx::Rect* top, 195 gfx::Rect* middle, 196 gfx::Rect* bottom) const { 197 size_t n = rects.size(); 198 199 // Figure out how many rects belong in the top portion. 200 gfx::Rect top_rect = rects[0]; 201 int top_middle = (top_rect.y() + top_rect.bottom()) / 2; 202 size_t top_count = 1; 203 while (top_count < n && rects[top_count].y() < top_middle) { 204 top_rect.Union(rects[top_count]); 205 top_middle = (top_rect.y() + top_rect.bottom()) / 2; 206 top_count++; 207 } 208 209 // Figure out how many rects belong in the bottom portion. 210 gfx::Rect bottom_rect = rects[n - 1]; 211 int bottom_middle = (bottom_rect.y() + bottom_rect.bottom()) / 2; 212 size_t bottom_count = std::min(static_cast<size_t>(1), n - top_count); 213 while (bottom_count + top_count < n && 214 rects[n - bottom_count - 1].bottom() > bottom_middle) { 215 bottom_rect.Union(rects[n - bottom_count - 1]); 216 bottom_middle = (bottom_rect.y() + bottom_rect.bottom()) / 2; 217 bottom_count++; 218 } 219 220 // Whatever's left goes to the middle rect, but if there's no middle or 221 // bottom rect, split the existing rects evenly to make one. 222 gfx::Rect middle_rect; 223 if (top_count + bottom_count < n) { 224 middle_rect = rects[top_count]; 225 for (size_t i = top_count + 1; i < n - bottom_count; i++) 226 middle_rect.Union(rects[i]); 227 } else if (bottom_count > 0) { 228 gfx::Rect enclosing_rect = top_rect; 229 enclosing_rect.Union(bottom_rect); 230 int middle_top = (top_rect.y() + top_rect.bottom() * 2) / 3; 231 int middle_bottom = (bottom_rect.y() * 2 + bottom_rect.bottom()) / 3; 232 top_rect.set_height(middle_top - top_rect.y()); 233 bottom_rect.set_height(bottom_rect.bottom() - middle_bottom); 234 bottom_rect.set_y(middle_bottom); 235 middle_rect = gfx::Rect(enclosing_rect.x(), middle_top, 236 enclosing_rect.width(), middle_bottom - middle_top); 237 } else { 238 int middle_top = (top_rect.y() * 2 + top_rect.bottom()) / 3; 239 int middle_bottom = (top_rect.y() + top_rect.bottom() * 2) / 3; 240 middle_rect = gfx::Rect(top_rect.x(), middle_top, 241 top_rect.width(), middle_bottom - middle_top); 242 bottom_rect = gfx::Rect( 243 top_rect.x(), middle_bottom, 244 top_rect.width(), top_rect.bottom() - middle_bottom); 245 top_rect.set_height(middle_top - top_rect.y()); 246 } 247 248 if (middle_rect.y() > top_rect.bottom()) { 249 middle_rect.set_height( 250 middle_rect.height() + middle_rect.y() - top_rect.bottom()); 251 middle_rect.set_y(top_rect.bottom()); 252 } 253 254 if (middle_rect.bottom() < bottom_rect.y()) { 255 middle_rect.set_height(bottom_rect.y() - middle_rect.y()); 256 } 257 258 *top = top_rect; 259 *middle = middle_rect; 260 *bottom = bottom_rect; 261} 262 263AccessibilityFocusRing AccessibilityFocusRingController::RingFromSortedRects( 264 const std::vector<gfx::Rect>& rects) const { 265 if (rects.size() == 1) 266 return AccessibilityFocusRing::CreateWithRect(rects[0], GetMargin()); 267 268 gfx::Rect top; 269 gfx::Rect middle; 270 gfx::Rect bottom; 271 SplitIntoParagraphShape(rects, &top, &middle, &bottom); 272 273 return AccessibilityFocusRing::CreateWithParagraphShape( 274 top, middle, bottom, GetMargin()); 275} 276 277bool AccessibilityFocusRingController::Intersects( 278 const gfx::Rect& r1, const gfx::Rect& r2) const { 279 int slop = GetMargin(); 280 return (r2.x() <= r1.right() + slop && 281 r2.right() >= r1.x() - slop && 282 r2.y() <= r1.bottom() + slop && 283 r2.bottom() >= r1.y() - slop); 284} 285 286void AccessibilityFocusRingController::OnDeviceScaleFactorChanged() { 287 Update(); 288} 289 290void AccessibilityFocusRingController::OnAnimationStep( 291 base::TimeTicks timestamp) { 292 if (rings_.empty()) 293 return; 294 295 CHECK(compositor_); 296 CHECK(!rings_.empty()); 297 CHECK(!layers_.empty()); 298 CHECK(layers_[0]); 299 300 // It's quite possible for the first 1 or 2 animation frames to be 301 // for a timestamp that's earlier than the time we received the 302 // focus change, so we just treat those as a delta of zero. 303 if (timestamp < focus_change_time_) 304 timestamp = focus_change_time_; 305 306 base::TimeDelta delta = timestamp - focus_change_time_; 307 base::TimeDelta transition_time = 308 base::TimeDelta::FromMilliseconds(kTransitionTimeMilliseconds); 309 if (delta >= transition_time) { 310 layers_[0]->Set(rings_[0]); 311 compositor_->RemoveAnimationObserver(this); 312 compositor_ = NULL; 313 return; 314 } 315 316 double fraction = delta.InSecondsF() / transition_time.InSecondsF(); 317 318 // Ease-in effect. 319 fraction = pow(fraction, 0.3); 320 321 layers_[0]->Set(AccessibilityFocusRing::Interpolate( 322 previous_rings_[0], rings_[0], fraction)); 323} 324 325} // namespace chromeos 326