| // Copyright 2013 The Flutter 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 "flutter/display_list/display_list_rtree.h" |
| #include "gtest/gtest.h" |
| #include "third_party/skia/include/core/SkRect.h" |
| |
| namespace flutter { |
| namespace testing { |
| |
| #ifndef NDEBUG |
| TEST(DisplayListRTree, NullRectListNonZeroCount) { |
| EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, 1), "rects != nullptr"); |
| } |
| |
| TEST(DisplayListRTree, NegativeCount) { |
| EXPECT_DEATH_IF_SUPPORTED(new DlRTree(nullptr, -1), "N >= 0"); |
| } |
| |
| TEST(DisplayListRTree, NullSearchResultVector) { |
| DlRTree tree(nullptr, 0); |
| EXPECT_DEATH_IF_SUPPORTED(tree.search(SkRect::MakeLTRB(0, 0, 1, 1), nullptr), |
| "results != nullptr"); |
| } |
| #endif |
| |
| TEST(DisplayListRTree, NullRectListZeroCount) { |
| DlRTree tree(nullptr, 0); |
| EXPECT_EQ(tree.leaf_count(), 0); |
| EXPECT_EQ(tree.node_count(), 0); |
| std::vector<int> results; |
| auto huge = SkRect::MakeLTRB(-1e6, -1e6, 1e6, 1e6); |
| tree.search(huge, &results); |
| EXPECT_EQ(results.size(), 0u); |
| auto list = tree.searchAndConsolidateRects(huge); |
| EXPECT_EQ(list.size(), 0u); |
| } |
| |
| TEST(DisplayListRTree, ManySizes) { |
| // A diagonal of non-overlapping 10x10 rectangles spaced 20 |
| // pixels apart. |
| // Rect 1 goes from 0 to 10 |
| // Rect 2 goes from 20 to 30 |
| // etc. in both dimensions |
| const int kMaxN = 250; |
| SkRect rects[kMaxN + 1]; |
| int ids[kMaxN + 1]; |
| for (int i = 0; i <= kMaxN; i++) { |
| rects[i].setXYWH(i * 20, i * 20, 10, 10); |
| ids[i] = i + 42; |
| } |
| std::vector<int> results; |
| for (int N = 0; N <= kMaxN; N++) { |
| DlRTree tree(rects, N, ids); |
| auto desc = "node count = " + std::to_string(N); |
| EXPECT_EQ(tree.leaf_count(), N) << desc; |
| EXPECT_GE(tree.node_count(), N) << desc; |
| EXPECT_EQ(tree.id(-1), -1) << desc; |
| EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty()) << desc; |
| EXPECT_EQ(tree.id(N), -1) << desc; |
| EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty()) << desc; |
| results.clear(); |
| tree.search(SkRect::MakeEmpty(), &results); |
| EXPECT_EQ(results.size(), 0u) << desc; |
| results.clear(); |
| tree.search(SkRect::MakeLTRB(2, 2, 8, 8), &results); |
| if (N == 0) { |
| EXPECT_EQ(results.size(), 0u) << desc; |
| } else { |
| EXPECT_EQ(results.size(), 1u) << desc; |
| EXPECT_EQ(results[0], 0) << desc; |
| EXPECT_EQ(tree.id(results[0]), ids[0]) << desc; |
| EXPECT_EQ(tree.bounds(results[0]), rects[0]) << desc; |
| for (int i = 1; i < N; i++) { |
| results.clear(); |
| auto query = SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6); |
| tree.search(query, &results); |
| EXPECT_EQ(results.size(), 1u) << desc; |
| EXPECT_EQ(results[0], i) << desc; |
| EXPECT_EQ(tree.id(results[0]), ids[i]) << desc; |
| EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc; |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), rects[i]); |
| } |
| } |
| } |
| } |
| |
| TEST(DisplayListRTree, HugeSize) { |
| // A diagonal of non-overlapping 10x10 rectangles spaced 20 |
| // pixels apart. |
| // Rect 1 goes from 0 to 10 |
| // Rect 2 goes from 20 to 30 |
| // etc. in both dimensions |
| const int N = 10000; |
| SkRect rects[N]; |
| int ids[N]; |
| for (int i = 0; i < N; i++) { |
| rects[i].setXYWH(i * 20, i * 20, 10, 10); |
| ids[i] = i + 42; |
| } |
| DlRTree tree(rects, N, ids); |
| EXPECT_EQ(tree.leaf_count(), N); |
| EXPECT_GE(tree.node_count(), N); |
| EXPECT_EQ(tree.id(-1), -1); |
| EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty()); |
| EXPECT_EQ(tree.id(N), -1); |
| EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty()); |
| std::vector<int> results; |
| tree.search(SkRect::MakeEmpty(), &results); |
| EXPECT_EQ(results.size(), 0u); |
| for (int i = 0; i < N; i++) { |
| results.clear(); |
| tree.search(SkRect::MakeXYWH(i * 20 + 2, i * 20 + 2, 6, 6), &results); |
| EXPECT_EQ(results.size(), 1u); |
| EXPECT_EQ(results[0], i); |
| EXPECT_EQ(tree.id(results[0]), ids[i]); |
| EXPECT_EQ(tree.bounds(results[0]), rects[i]); |
| } |
| } |
| |
| TEST(DisplayListRTree, Grid) { |
| // Non-overlapping 10 x 10 rectangles starting at 5, 5 with |
| // 10 pixels between them. |
| // Rect 1 goes from 5 to 15 |
| // Rect 2 goes from 25 to 35 |
| // etc. in both dimensions |
| const int ROWS = 10; |
| const int COLS = 10; |
| const int N = ROWS * COLS; |
| SkRect rects[N]; |
| int ids[N]; |
| for (int r = 0; r < ROWS; r++) { |
| int y = r * 20 + 5; |
| for (int c = 0; c < COLS; c++) { |
| int x = c * 20 + 5; |
| int i = r * COLS + c; |
| rects[i] = SkRect::MakeXYWH(x, y, 10, 10); |
| ids[i] = i + 42; |
| } |
| } |
| DlRTree tree(rects, N, ids); |
| EXPECT_EQ(tree.leaf_count(), N); |
| EXPECT_GE(tree.node_count(), N); |
| EXPECT_EQ(tree.id(-1), -1); |
| EXPECT_EQ(tree.bounds(-1), SkRect::MakeEmpty()); |
| EXPECT_EQ(tree.id(N), -1); |
| EXPECT_EQ(tree.bounds(N), SkRect::MakeEmpty()); |
| std::vector<int> results; |
| tree.search(SkRect::MakeEmpty(), &results); |
| EXPECT_EQ(results.size(), 0u); |
| // Testing eqch rect for a single hit |
| for (int r = 0; r < ROWS; r++) { |
| int y = r * 20 + 5; |
| for (int c = 0; c < COLS; c++) { |
| int x = c * 20 + 5; |
| int i = r * COLS + c; |
| auto desc = |
| "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1); |
| results.clear(); |
| auto query = SkRect::MakeXYWH(x + 2, y + 2, 6, 6); |
| tree.search(query, &results); |
| EXPECT_EQ(results.size(), 1u) << desc; |
| EXPECT_EQ(results[0], i) << desc; |
| EXPECT_EQ(tree.id(results[0]), ids[i]) << desc; |
| EXPECT_EQ(tree.bounds(results[0]), rects[i]) << desc; |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), rects[i]); |
| } |
| } |
| // Testing inside each gap for no hits |
| for (int r = 1; r < ROWS; r++) { |
| int y = r * 20 + 5; |
| for (int c = 1; c < COLS; c++) { |
| int x = c * 20 + 5; |
| auto desc = |
| "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1); |
| results.clear(); |
| auto query = SkRect::MakeXYWH(x - 8, y - 8, 6, 6); |
| tree.search(query, &results); |
| EXPECT_EQ(results.size(), 0u) << desc; |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 0u) << desc; |
| } |
| } |
| // Spanning each gap for a quad of hits |
| for (int r = 1; r < ROWS; r++) { |
| int y = r * 20 + 5; |
| for (int c = 1; c < COLS; c++) { |
| int x = c * 20 + 5; |
| // We will hit this rect and the ones above/left of us |
| int i = r * COLS + c; |
| auto desc = |
| "row " + std::to_string(r + 1) + ", col " + std::to_string(c + 1); |
| results.clear(); |
| auto query = SkRect::MakeXYWH(x - 11, y - 11, 12, 12); |
| tree.search(query, &results); |
| EXPECT_EQ(results.size(), 4u) << desc; |
| |
| // First rect is above and to the left |
| EXPECT_EQ(results[0], i - COLS - 1) << desc; |
| EXPECT_EQ(tree.id(results[0]), ids[i - COLS - 1]) << desc; |
| EXPECT_EQ(tree.bounds(results[0]), rects[i - COLS - 1]) << desc; |
| |
| // Second rect is above |
| EXPECT_EQ(results[1], i - COLS) << desc; |
| EXPECT_EQ(tree.id(results[1]), ids[i - COLS]) << desc; |
| EXPECT_EQ(tree.bounds(results[1]), rects[i - COLS]) << desc; |
| |
| // Third rect is left |
| EXPECT_EQ(results[2], i - 1) << desc; |
| EXPECT_EQ(tree.id(results[2]), ids[i - 1]) << desc; |
| EXPECT_EQ(tree.bounds(results[2]), rects[i - 1]) << desc; |
| |
| // Fourth rect is us |
| EXPECT_EQ(results[3], i) << desc; |
| EXPECT_EQ(tree.id(results[3]), ids[i]) << desc; |
| EXPECT_EQ(tree.bounds(results[3]), rects[i]) << desc; |
| |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 4u); |
| list.remove(rects[i - COLS - 1]); |
| list.remove(rects[i - COLS]); |
| list.remove(rects[i - 1]); |
| list.remove(rects[i]); |
| EXPECT_EQ(list.size(), 0u); |
| } |
| } |
| } |
| |
| TEST(DisplayListRTree, OverlappingRects) { |
| // Rectangles are centered at coordinates 15, 35, and 55 and are 15 wide |
| // This gives them 10 pixels of overlap with the rectangles on either |
| // side of them and the 10 pixels around their center coordinate are |
| // exclusive to themselves. |
| // So, horizontally and vertically, they cover the following ranges: |
| // First row/col: 0 to 30 |
| // Second row/col: 20 to 50 |
| // Third row/col: 40 to 70 |
| // Coords 0 to 20 are only the first row/col |
| // Coords 20 to 30 are both first and second row/col |
| // Coords 30 to 40 are only the second row/col |
| // Coords 40 to 50 are both second and third row/col |
| // Coords 50 to 70 are only the third row/col |
| // |
| // In either dimension: |
| // 0------------------20--------30--------40--------50------------------70 |
| // | rect1 | |
| // | 1 & 2 | |
| // | rect2 | |
| // | 2 & 3 | |
| // | rect3 | |
| SkRect rects[9]; |
| for (int r = 0; r < 3; r++) { |
| int y = 15 + 20 * r; |
| for (int c = 0; c < 3; c++) { |
| int x = 15 + 20 * c; |
| rects[r * 3 + c].setLTRB(x - 15, y - 15, x + 15, y + 15); |
| } |
| } |
| DlRTree tree(rects, 9); |
| // Tiny rects only intersecting a single source rect |
| for (int r = 0; r < 3; r++) { |
| int y = 15 + 20 * r; |
| for (int c = 0; c < 3; c++) { |
| int x = 15 + 20 * c; |
| auto query = SkRect::MakeLTRB(x - 1, y - 1, x + 1, y + 1); |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), rects[r * 3 + c]); |
| } |
| } |
| // Wide rects intersecting 3 source rects horizontally |
| for (int r = 0; r < 3; r++) { |
| int c = 1; |
| int y = 15 + 20 * r; |
| int x = 15 + 20 * c; |
| auto query = SkRect::MakeLTRB(x - 6, y - 1, x + 6, y + 1); |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 35, y - 15, x + 35, y + 15)); |
| } |
| // Tall rects intersecting 3 source rects vertically |
| for (int c = 0; c < 3; c++) { |
| int r = 1; |
| int x = 15 + 20 * c; |
| int y = 15 + 20 * r; |
| auto query = SkRect::MakeLTRB(x - 1, y - 6, x + 1, y + 6); |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), SkRect::MakeLTRB(x - 15, y - 35, x + 15, y + 35)); |
| } |
| // Finally intersecting all 9 rects |
| auto query = SkRect::MakeLTRB(35 - 6, 35 - 6, 35 + 6, 35 + 6); |
| auto list = tree.searchAndConsolidateRects(query); |
| EXPECT_EQ(list.size(), 1u); |
| EXPECT_EQ(list.front(), SkRect::MakeLTRB(0, 0, 70, 70)); |
| } |
| |
| } // namespace testing |
| } // namespace flutter |