rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 8 | #include "SkRTree.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 9 | #include "SkRandom.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 10 | #include "SkTSort.h" |
tfarina@chromium.org | 8f6884a | 2014-01-24 20:56:26 +0000 | [diff] [blame] | 11 | #include "Test.h" |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 12 | |
| 13 | static const size_t MIN_CHILDREN = 6; |
| 14 | static const size_t MAX_CHILDREN = 11; |
| 15 | |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 16 | static const int NUM_RECTS = 200; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 17 | static const size_t NUM_ITERATIONS = 100; |
| 18 | static const size_t NUM_QUERIES = 50; |
| 19 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 20 | static SkRect random_rect(SkRandom& rand) { |
| 21 | SkRect rect = {0,0,0,0}; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 22 | while (rect.isEmpty()) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 23 | rect.fLeft = rand.nextRangeF(0, 1000); |
| 24 | rect.fRight = rand.nextRangeF(0, 1000); |
| 25 | rect.fTop = rand.nextRangeF(0, 1000); |
| 26 | rect.fBottom = rand.nextRangeF(0, 1000); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 27 | rect.sort(); |
| 28 | } |
| 29 | return rect; |
| 30 | } |
| 31 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 32 | static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 33 | // TODO(mtklein): no need to do this after everything's SkRects |
| 34 | query.roundOut(); |
| 35 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 36 | SkTDArray<unsigned> expected; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 37 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 38 | // manually intersect with every rectangle |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 39 | for (int i = 0; i < NUM_RECTS; ++i) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 40 | if (SkRect::Intersects(query, rects[i])) { |
| 41 | expected.push(i); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 42 | } |
| 43 | } |
| 44 | |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 45 | if (expected.count() != found.count()) { |
| 46 | return false; |
| 47 | } |
| 48 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 49 | if (0 == expected.count()) { |
| 50 | return true; |
| 51 | } |
| 52 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 53 | // skia:2834. RTree doesn't always return results in order. |
| 54 | SkTQSort(expected.begin(), expected.end() -1); |
| 55 | SkTQSort(found.begin(), found.end() -1); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 56 | return found == expected; |
| 57 | } |
| 58 | |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 59 | static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[], |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 60 | SkRTree& tree) { |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 61 | for (size_t i = 0; i < NUM_QUERIES; ++i) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 62 | SkTDArray<unsigned> hits; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 63 | SkRect query = random_rect(rand); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 64 | tree.search(query, &hits); |
| 65 | REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 66 | } |
| 67 | } |
| 68 | |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 69 | static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 70 | SkASSERT(rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 71 | |
| 72 | int expectedDepthMin = -1; |
| 73 | int expectedDepthMax = -1; |
| 74 | |
| 75 | int tmp = NUM_RECTS; |
| 76 | while (tmp > 0) { |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 77 | tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 78 | static_cast<double>(expectedDepthMin + 1))); |
| 79 | ++expectedDepthMin; |
| 80 | } |
| 81 | |
| 82 | tmp = NUM_RECTS; |
| 83 | while (tmp > 0) { |
| 84 | tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), |
| 85 | static_cast<double>(expectedDepthMax + 1))); |
| 86 | ++expectedDepthMax; |
| 87 | } |
| 88 | |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 89 | SkRandom rand; |
| 90 | SkAutoTMalloc<SkRect> rects(NUM_RECTS); |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 91 | for (size_t i = 0; i < NUM_ITERATIONS; ++i) { |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 92 | rtree->clear(); |
| 93 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 94 | |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 95 | for (int j = 0; j < NUM_RECTS; j++) { |
| 96 | rects[j] = random_rect(rand); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 97 | } |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 98 | |
| 99 | rtree->insert(&rects, NUM_RECTS); |
| 100 | SkASSERT(rects); // SkRTree doesn't take ownership of rects. |
| 101 | |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 102 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 103 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 104 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 105 | expectedDepthMax >= rtree->getDepth()); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 106 | } |
| 107 | } |
| 108 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 109 | DEF_TEST(RTree, reporter) { |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 110 | SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); |
| 111 | SkAutoUnref au(rtree); |
| 112 | rtree_test_main(rtree, reporter); |
| 113 | |
| 114 | // Rtree that orders input rectangles on deferred insert. |
sglez@google.com | ffb71f2 | 2013-08-30 17:43:31 +0000 | [diff] [blame] | 115 | SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false); |
| 116 | SkAutoUnref auo(unsortedRtree); |
| 117 | rtree_test_main(unsortedRtree, reporter); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 118 | } |