collision_detection_utils.cc 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421
  1. // Copyright 2019 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. #include "ash/wm/collision_detection/collision_detection_utils.h"
  5. #include "ash/app_list/app_list_controller_impl.h"
  6. #include "ash/capture_mode/capture_mode_camera_controller.h"
  7. #include "ash/capture_mode/capture_mode_controller.h"
  8. #include "ash/capture_mode/capture_mode_session.h"
  9. #include "ash/constants/ash_features.h"
  10. #include "ash/keyboard/ui/keyboard_ui_controller.h"
  11. #include "ash/public/cpp/shelf_types.h"
  12. #include "ash/public/cpp/shell_window_ids.h"
  13. #include "ash/shelf/shelf.h"
  14. #include "ash/shelf/shelf_layout_manager.h"
  15. #include "ash/shell.h"
  16. #include "ash/system/message_center/ash_message_popup_collection.h"
  17. #include "ash/wm/work_area_insets.h"
  18. #include "ui/base/class_property.h"
  19. #include "ui/views/widget/widget.h"
  20. #include "ui/wm/core/coordinate_conversion.h"
  21. DEFINE_UI_CLASS_PROPERTY_TYPE(ash::CollisionDetectionUtils::RelativePriority)
  22. namespace ash {
  23. namespace {
  24. // A property key to store whether the a window should be ignored for window
  25. // collision detection. For example, StatusBubble windows.
  26. DEFINE_UI_CLASS_PROPERTY_KEY(bool, kIgnoreForWindowCollisionDetection, false)
  27. // A property key to store a window's collision detection priority, used to
  28. // resolve collisions between multiple windows which are both using
  29. // CollisionDetectionUtils.
  30. DEFINE_UI_CLASS_PROPERTY_KEY(
  31. CollisionDetectionUtils::RelativePriority,
  32. kCollisionDetectionRelativePriority,
  33. CollisionDetectionUtils::RelativePriority::kDefault)
  34. bool ShouldIgnoreWindowForCollision(
  35. const aura::Window* window,
  36. CollisionDetectionUtils::RelativePriority priority) {
  37. if (window->GetProperty(kIgnoreForWindowCollisionDetection))
  38. return true;
  39. DCHECK_NE(CollisionDetectionUtils::RelativePriority::kDefault, priority);
  40. // Only ignore a window if our priority is greater than theirs. Lower priority
  41. // windows need to move for higher priority windows, and windows do not need
  42. // to move for a window of their own priority.
  43. return static_cast<int>(priority) >=
  44. static_cast<int>(
  45. window->GetProperty(kCollisionDetectionRelativePriority));
  46. }
  47. gfx::Rect ComputeCollisionRectFromBounds(const gfx::Rect& bounds,
  48. const aura::Window* parent,
  49. bool inset = true) {
  50. gfx::Rect collision_rect = bounds;
  51. ::wm::ConvertRectToScreen(parent, &collision_rect);
  52. if (inset) {
  53. collision_rect.Inset(-kCollisionWindowWorkAreaInsetsDp);
  54. }
  55. return collision_rect;
  56. }
  57. std::vector<gfx::Rect> CollectCollisionRects(
  58. const display::Display& display,
  59. CollisionDetectionUtils::RelativePriority priority) {
  60. DCHECK_NE(CollisionDetectionUtils::RelativePriority::kDefault, priority);
  61. std::vector<gfx::Rect> rects;
  62. auto* root_window = Shell::GetRootWindowForDisplayId(display.id());
  63. if (root_window) {
  64. // Check SettingsBubbleContainer windows.
  65. auto* settings_bubble_container =
  66. root_window->GetChildById(kShellWindowId_SettingBubbleContainer);
  67. for (auto* window : settings_bubble_container->children()) {
  68. if (!window->IsVisible() && !window->GetTargetBounds().IsEmpty())
  69. continue;
  70. if (ShouldIgnoreWindowForCollision(window, priority))
  71. continue;
  72. // Use the target bounds in case an animation is in progress.
  73. rects.push_back(ComputeCollisionRectFromBounds(window->GetTargetBounds(),
  74. window->parent()));
  75. }
  76. // Check auto-hide shelf, which isn't included normally in the work area:
  77. auto* shelf = Shelf::ForWindow(root_window);
  78. auto* shelf_window = shelf->GetWindow();
  79. if (shelf->IsVisible() &&
  80. !ShouldIgnoreWindowForCollision(shelf_window, priority)) {
  81. rects.push_back(ComputeCollisionRectFromBounds(
  82. shelf_window->GetTargetBounds(), shelf_window->parent()));
  83. }
  84. // Explicitly add popup notifications as they are not in the notification
  85. // tray.
  86. auto* shelf_container =
  87. root_window->GetChildById(kShellWindowId_ShelfContainer);
  88. for (auto* window : shelf_container->children()) {
  89. if (window->IsVisible() && !window->GetTargetBounds().IsEmpty() &&
  90. window->GetName() ==
  91. AshMessagePopupCollection::kMessagePopupWidgetName &&
  92. !ShouldIgnoreWindowForCollision(window, priority)) {
  93. rects.push_back(ComputeCollisionRectFromBounds(
  94. window->GetTargetBounds(), window->parent()));
  95. }
  96. }
  97. // The hotseat doesn't span the whole width of the display, but to allow
  98. // a PIP window to be slided horizontally along the hotseat, we extend the
  99. // width of the hotseat to that of the display.
  100. auto* hotseat_widget = shelf->hotseat_widget();
  101. if (hotseat_widget) {
  102. auto* hotseat_window = hotseat_widget->GetNativeWindow();
  103. gfx::Rect hotseat_rect{root_window->bounds().x(),
  104. hotseat_window->GetTargetBounds().y(),
  105. root_window->bounds().width(),
  106. hotseat_window->GetTargetBounds().height()};
  107. if (hotseat_widget->state() != HotseatState::kHidden &&
  108. hotseat_widget->state() != HotseatState::kNone &&
  109. !ShouldIgnoreWindowForCollision(hotseat_window, priority)) {
  110. rects.push_back(ComputeCollisionRectFromBounds(
  111. hotseat_rect, hotseat_window->parent()));
  112. }
  113. }
  114. // Check the Automatic Clicks windows.
  115. // TODO(Katie): The PIP isn't re-triggered to check the accessibility bubble
  116. // windows when the autoclick window moves, just when the PIP moves or
  117. // another system window. Need to ensure that changing the autoclick menu
  118. // position triggers the PIP to re-check its bounds. crbug.com/954546.
  119. auto* accessibility_bubble_container =
  120. root_window->GetChildById(kShellWindowId_AccessibilityBubbleContainer);
  121. for (auto* window : accessibility_bubble_container->children()) {
  122. if (!window->IsVisible() && !window->GetTargetBounds().IsEmpty())
  123. continue;
  124. if (ShouldIgnoreWindowForCollision(window, priority))
  125. continue;
  126. // Use the target bounds in case an animation is in progress.
  127. if (priority ==
  128. CollisionDetectionUtils::RelativePriority::kAutomaticClicksMenu &&
  129. window->GetProperty(kCollisionDetectionRelativePriority) ==
  130. CollisionDetectionUtils::RelativePriority::
  131. kAutomaticClicksScrollMenu) {
  132. // The autoclick menu widget and autoclick scroll menu widget are 0dip
  133. // apart because they must be drawn at 8dips apart including drop
  134. // shadow. This special case means we should not add an inset if we
  135. // are calculating collision rects for the autoclick menu.
  136. rects.push_back(ComputeCollisionRectFromBounds(
  137. window->GetTargetBounds(), window->parent(),
  138. false /* do not inset */));
  139. } else {
  140. rects.push_back(ComputeCollisionRectFromBounds(
  141. window->GetTargetBounds(), window->parent()));
  142. }
  143. }
  144. }
  145. auto* keyboard_controller = keyboard::KeyboardUIController::Get();
  146. if (keyboard_controller->IsEnabled() &&
  147. keyboard_controller->GetActiveContainerType() ==
  148. keyboard::ContainerType::kFloating &&
  149. keyboard_controller->GetRootWindow() == root_window &&
  150. !keyboard_controller->GetVisualBoundsInScreen().IsEmpty() &&
  151. !ShouldIgnoreWindowForCollision(keyboard_controller->GetKeyboardWindow(),
  152. priority)) {
  153. rects.push_back(ComputeCollisionRectFromBounds(
  154. keyboard_controller->visual_bounds_in_root(),
  155. /*parent=*/root_window));
  156. }
  157. // Check the capture bar if capture mode is active.
  158. auto* capture_mode_controller = CaptureModeController::Get();
  159. if (capture_mode_controller->IsActive()) {
  160. aura::Window* capture_bar_window =
  161. capture_mode_controller->capture_mode_session()
  162. ->capture_mode_bar_widget()
  163. ->GetNativeWindow();
  164. rects.push_back(ComputeCollisionRectFromBounds(
  165. capture_bar_window->GetTargetBounds(), capture_bar_window->parent()));
  166. }
  167. // Check the camera preview if it exists.
  168. auto* camera_preview_widget =
  169. capture_mode_controller->camera_controller()->camera_preview_widget();
  170. if (camera_preview_widget && camera_preview_widget->IsVisible()) {
  171. aura::Window* camera_preview_window =
  172. camera_preview_widget->GetNativeWindow();
  173. rects.push_back(
  174. ComputeCollisionRectFromBounds(camera_preview_window->GetTargetBounds(),
  175. camera_preview_window->parent()));
  176. }
  177. // Avoid clamshell-mode launcher bubble.
  178. auto* app_list_controller = Shell::Get()->app_list_controller();
  179. if (features::IsProductivityLauncherEnabled() &&
  180. !Shell::Get()->IsInTabletMode() &&
  181. app_list_controller->GetTargetVisibility(display.id())) {
  182. aura::Window* window = app_list_controller->GetWindow();
  183. if (window) {
  184. rects.push_back(ComputeCollisionRectFromBounds(window->GetTargetBounds(),
  185. window->parent()));
  186. }
  187. }
  188. return rects;
  189. }
  190. // Finds the candidate points |center| could be moved to. One of these points
  191. // is guaranteed to be the minimum distance to move |center| to make it not
  192. // intersect any of the rectangles in |collision_rects|.
  193. std::vector<gfx::Point> CollectCandidatePoints(
  194. const gfx::Point& center,
  195. const std::vector<gfx::Rect>& collision_rects) {
  196. std::vector<gfx::Point> candidate_points;
  197. candidate_points.reserve(4 * collision_rects.size() * collision_rects.size() +
  198. 4 * collision_rects.size() + 1);
  199. // There are four cases for how the window will move.
  200. // Case #1: Touches 0 obstacles. This corresponds to not moving.
  201. // Case #2: Touches 1 obstacle.
  202. // The result window will be touching one edge of the obstacle.
  203. // Case #3: Touches 2 obstacles.
  204. // The result window will be touching one horizontal and one vertical edge
  205. // from two different obstacles.
  206. // Case #4: Touches more than 2 obstacles. This is handled in case #3.
  207. // Case #2.
  208. // Rects include the left and top edges, so subtract 1 for those.
  209. // Prioritize horizontal movement before vertical movement.
  210. bool intersects = false;
  211. for (const auto& rectA : collision_rects) {
  212. intersects = intersects || rectA.Contains(center);
  213. candidate_points.emplace_back(rectA.x() - 1, center.y());
  214. candidate_points.emplace_back(rectA.right(), center.y());
  215. candidate_points.emplace_back(center.x(), rectA.y() - 1);
  216. candidate_points.emplace_back(center.x(), rectA.bottom());
  217. }
  218. // Case #1: Touching zero obstacles, so don't move the window.
  219. if (!intersects)
  220. return {};
  221. // Case #3: Add candidate points corresponding to each pair of horizontal
  222. // and vertical edges.
  223. for (const auto& rectA : collision_rects) {
  224. for (const auto& rectB : collision_rects) {
  225. // Continuing early here isn't necessary but makes fewer candidate points.
  226. if (&rectA == &rectB)
  227. continue;
  228. candidate_points.emplace_back(rectA.x() - 1, rectB.y() - 1);
  229. candidate_points.emplace_back(rectA.x() - 1, rectB.bottom());
  230. candidate_points.emplace_back(rectA.right(), rectB.y() - 1);
  231. candidate_points.emplace_back(rectA.right(), rectB.bottom());
  232. }
  233. }
  234. return candidate_points;
  235. }
  236. // Finds the candidate point with the shortest distance to |center| that is
  237. // inside |work_area| and does not intersect any gfx::Rect in |rects|.
  238. gfx::Point ComputeBestCandidatePoint(const gfx::Point& center,
  239. const gfx::Rect& work_area,
  240. const std::vector<gfx::Rect>& rects) {
  241. auto candidate_points = CollectCandidatePoints(center, rects);
  242. int64_t best_dist = -1;
  243. gfx::Point best_point = center;
  244. for (const auto& point : candidate_points) {
  245. if (!work_area.Contains(point))
  246. continue;
  247. bool viable = true;
  248. for (const auto& rect : rects) {
  249. if (rect.Contains(point)) {
  250. viable = false;
  251. break;
  252. }
  253. }
  254. if (!viable)
  255. continue;
  256. int64_t dist = (point - center).LengthSquared();
  257. if (dist < best_dist || best_dist == -1) {
  258. best_dist = dist;
  259. best_point = point;
  260. }
  261. }
  262. return best_point;
  263. }
  264. } // namespace
  265. gfx::Rect CollisionDetectionUtils::GetMovementArea(
  266. const display::Display& display) {
  267. gfx::Rect work_area =
  268. WorkAreaInsets::ForWindow(Shell::GetRootWindowForDisplayId(display.id()))
  269. ->user_work_area_bounds();
  270. work_area.Inset(kCollisionWindowWorkAreaInsetsDp);
  271. return work_area;
  272. }
  273. gfx::Rect CollisionDetectionUtils::AdjustToFitMovementAreaByGravity(
  274. const display::Display& display,
  275. const gfx::Rect& bounds_in_screen) {
  276. gfx::Rect resting_bounds = bounds_in_screen;
  277. gfx::Rect area = GetMovementArea(display);
  278. resting_bounds.AdjustToFit(area);
  279. const CollisionDetectionUtils::Gravity gravity =
  280. GetGravityToClosestEdge(resting_bounds, area);
  281. return GetAdjustedBoundsByGravity(resting_bounds, area, gravity);
  282. }
  283. gfx::Rect CollisionDetectionUtils::GetRestingPosition(
  284. const display::Display& display,
  285. const gfx::Rect& bounds_in_screen,
  286. CollisionDetectionUtils::RelativePriority priority) {
  287. gfx::Rect resting_bounds =
  288. AdjustToFitMovementAreaByGravity(display, bounds_in_screen);
  289. return AvoidObstacles(display, resting_bounds, priority);
  290. }
  291. void CollisionDetectionUtils::IgnoreWindowForCollisionDetection(
  292. aura::Window* window) {
  293. window->SetProperty(kIgnoreForWindowCollisionDetection, true);
  294. }
  295. void CollisionDetectionUtils::MarkWindowPriorityForCollisionDetection(
  296. aura::Window* window,
  297. RelativePriority priority) {
  298. window->SetProperty(kCollisionDetectionRelativePriority, priority);
  299. }
  300. gfx::Rect CollisionDetectionUtils::AvoidObstacles(
  301. const display::Display& display,
  302. const gfx::Rect& bounds_in_screen,
  303. RelativePriority priority) {
  304. gfx::Rect work_area = GetMovementArea(display);
  305. auto rects = CollectCollisionRects(display, priority);
  306. // The worst case for this should be: floating keyboard + one system tray +
  307. // the volume shifter + autoclick bubble menu, which is 4 windows.
  308. DCHECK(rects.size() <= 15)
  309. << "CollisionDetectionUtils::AvoidObstacles is N^3 and "
  310. "should be optimized if there are a lot of "
  311. "windows. Please see crrev.com/c/1221427 for a "
  312. "description of an N^2 algorithm.";
  313. return AvoidObstaclesInternal(work_area, rects, bounds_in_screen, priority);
  314. }
  315. // Returns the result of adjusting |bounds| according to |gravity| inside
  316. // |region|.
  317. gfx::Rect CollisionDetectionUtils::GetAdjustedBoundsByGravity(
  318. const gfx::Rect& bounds,
  319. const gfx::Rect& region,
  320. CollisionDetectionUtils::Gravity gravity) {
  321. switch (gravity) {
  322. case CollisionDetectionUtils::Gravity::kGravityLeft:
  323. return gfx::Rect(region.x(), bounds.y(), bounds.width(), bounds.height());
  324. case CollisionDetectionUtils::Gravity::kGravityRight:
  325. return gfx::Rect(region.right() - bounds.width(), bounds.y(),
  326. bounds.width(), bounds.height());
  327. case CollisionDetectionUtils::Gravity::kGravityTop:
  328. return gfx::Rect(bounds.x(), region.y(), bounds.width(), bounds.height());
  329. case CollisionDetectionUtils::Gravity::kGravityBottom:
  330. return gfx::Rect(bounds.x(), region.bottom() - bounds.height(),
  331. bounds.width(), bounds.height());
  332. default:
  333. NOTREACHED();
  334. }
  335. return bounds;
  336. }
  337. CollisionDetectionUtils::Gravity
  338. CollisionDetectionUtils::GetGravityToClosestEdge(const gfx::Rect& bounds,
  339. const gfx::Rect& region) {
  340. const gfx::Insets insets = region.InsetsFrom(bounds);
  341. int minimum_edge_dist = std::min(insets.left(), insets.right());
  342. minimum_edge_dist = std::min(minimum_edge_dist, insets.top());
  343. minimum_edge_dist = std::min(minimum_edge_dist, insets.bottom());
  344. if (insets.left() == minimum_edge_dist) {
  345. return CollisionDetectionUtils::Gravity::kGravityLeft;
  346. } else if (insets.right() == minimum_edge_dist) {
  347. return CollisionDetectionUtils::Gravity::kGravityRight;
  348. } else if (insets.top() == minimum_edge_dist) {
  349. return CollisionDetectionUtils::Gravity::kGravityTop;
  350. } else {
  351. return CollisionDetectionUtils::Gravity::kGravityBottom;
  352. }
  353. }
  354. gfx::Rect CollisionDetectionUtils::AvoidObstaclesInternal(
  355. const gfx::Rect& work_area,
  356. const std::vector<gfx::Rect>& rects,
  357. const gfx::Rect& bounds_in_screen,
  358. RelativePriority priority) {
  359. gfx::Rect inset_work_area = work_area;
  360. // For even sized bounds, there is no 'center' integer point, so we need
  361. // to adjust the obstacles and work area to account for this.
  362. inset_work_area.Inset(gfx::Insets::TLBR(
  363. bounds_in_screen.height() / 2, bounds_in_screen.width() / 2,
  364. (bounds_in_screen.height() - 1) / 2, (bounds_in_screen.width() - 1) / 2));
  365. std::vector<gfx::Rect> inset_rects(rects);
  366. for (auto& rect : inset_rects) {
  367. // Reduce the collision resolution problem from rectangles-rectangle
  368. // resolution to rectangles-point resolution, by expanding each obstacle
  369. // by |bounds_in_screen| size.
  370. rect.Inset(gfx::Insets::TLBR(-(bounds_in_screen.height() - 1) / 2,
  371. -(bounds_in_screen.width() - 1) / 2,
  372. -bounds_in_screen.height() / 2,
  373. -bounds_in_screen.width() / 2));
  374. }
  375. gfx::Point moved_center = ComputeBestCandidatePoint(
  376. bounds_in_screen.CenterPoint(), inset_work_area, inset_rects);
  377. gfx::Rect moved_bounds = bounds_in_screen;
  378. moved_bounds.Offset(moved_center - bounds_in_screen.CenterPoint());
  379. return moved_bounds;
  380. }
  381. } // namespace ash