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 | |
| 20 | struct DataRect { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 21 | SkRect rect; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 22 | void* data; |
| 23 | }; |
| 24 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 25 | static SkRect random_rect(SkRandom& rand) { |
| 26 | SkRect rect = {0,0,0,0}; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 27 | while (rect.isEmpty()) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 28 | rect.fLeft = rand.nextRangeF(0, 1000); |
| 29 | rect.fRight = rand.nextRangeF(0, 1000); |
| 30 | rect.fTop = rand.nextRangeF(0, 1000); |
| 31 | rect.fBottom = rand.nextRangeF(0, 1000); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 32 | rect.sort(); |
| 33 | } |
| 34 | return rect; |
| 35 | } |
| 36 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 37 | static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 38 | for (int i = 0; i < n; ++i) { |
| 39 | out[i].rect = random_rect(rand); |
| 40 | out[i].data = reinterpret_cast<void*>(i); |
| 41 | } |
| 42 | } |
| 43 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 44 | static bool verify_query(SkRect query, DataRect rects[], |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 45 | SkTDArray<void*>& found) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 46 | // TODO(mtklein): no need to do this after everything's SkRects |
| 47 | query.roundOut(); |
| 48 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 49 | SkTDArray<void*> expected; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 50 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 51 | // manually intersect with every rectangle |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 52 | for (int i = 0; i < NUM_RECTS; ++i) { |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 53 | if (SkRect::Intersects(query, rects[i].rect)) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 54 | expected.push(rects[i].data); |
| 55 | } |
| 56 | } |
| 57 | |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 58 | if (expected.count() != found.count()) { |
| 59 | return false; |
| 60 | } |
| 61 | |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 62 | if (0 == expected.count()) { |
| 63 | return true; |
| 64 | } |
| 65 | |
| 66 | // Just cast to long since sorting by the value of the void*'s was being problematic... |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 67 | SkTQSort(reinterpret_cast<long*>(expected.begin()), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 68 | reinterpret_cast<long*>(expected.end() - 1)); |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 69 | SkTQSort(reinterpret_cast<long*>(found.begin()), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 70 | reinterpret_cast<long*>(found.end() - 1)); |
| 71 | return found == expected; |
| 72 | } |
| 73 | |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 74 | static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect rects[], |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 75 | SkRTree& tree) { |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 76 | for (size_t i = 0; i < NUM_QUERIES; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 77 | SkTDArray<void*> hits; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 78 | SkRect query = random_rect(rand); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 79 | tree.search(query, &hits); |
| 80 | REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 81 | } |
| 82 | } |
| 83 | |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 84 | static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 85 | DataRect rects[NUM_RECTS]; |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 86 | SkRandom rand; |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 87 | REPORTER_ASSERT(reporter, NULL != rtree); |
| 88 | |
| 89 | int expectedDepthMin = -1; |
| 90 | int expectedDepthMax = -1; |
| 91 | |
| 92 | int tmp = NUM_RECTS; |
| 93 | while (tmp > 0) { |
skia.committer@gmail.com | 6c77816 | 2012-09-06 02:01:13 +0000 | [diff] [blame] | 94 | tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN), |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 95 | static_cast<double>(expectedDepthMin + 1))); |
| 96 | ++expectedDepthMin; |
| 97 | } |
| 98 | |
| 99 | tmp = NUM_RECTS; |
| 100 | while (tmp > 0) { |
| 101 | tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN), |
| 102 | static_cast<double>(expectedDepthMax + 1))); |
| 103 | ++expectedDepthMax; |
| 104 | } |
| 105 | |
robertphillips@google.com | 178a267 | 2012-09-13 13:25:30 +0000 | [diff] [blame] | 106 | for (size_t i = 0; i < NUM_ITERATIONS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 107 | random_data_rects(rand, rects, NUM_RECTS); |
| 108 | |
| 109 | // First try bulk-loaded inserts |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 110 | for (int i = 0; i < NUM_RECTS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 111 | rtree->insert(rects[i].data, rects[i].rect, true); |
| 112 | } |
| 113 | rtree->flushDeferredInserts(); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 114 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 115 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 116 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 117 | expectedDepthMax >= rtree->getDepth()); |
| 118 | rtree->clear(); |
| 119 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 120 | |
| 121 | // Then try immediate inserts |
bsalomon@google.com | 373ebc6 | 2012-09-26 13:08:56 +0000 | [diff] [blame] | 122 | for (int i = 0; i < NUM_RECTS; ++i) { |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 123 | rtree->insert(rects[i].data, rects[i].rect); |
| 124 | } |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 125 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 126 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 127 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 128 | expectedDepthMax >= rtree->getDepth()); |
| 129 | rtree->clear(); |
| 130 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 131 | |
| 132 | // And for good measure try immediate inserts, but in reversed order |
| 133 | for (int i = NUM_RECTS - 1; i >= 0; --i) { |
| 134 | rtree->insert(rects[i].data, rects[i].rect); |
| 135 | } |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 136 | run_queries(reporter, rand, rects, *rtree); |
rileya@google.com | 1f45e93 | 2012-09-05 16:10:59 +0000 | [diff] [blame] | 137 | REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount()); |
| 138 | REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() && |
| 139 | expectedDepthMax >= rtree->getDepth()); |
| 140 | rtree->clear(); |
| 141 | REPORTER_ASSERT(reporter, 0 == rtree->getCount()); |
| 142 | } |
| 143 | } |
| 144 | |
tfarina@chromium.org | e4fafb1 | 2013-12-12 21:11:12 +0000 | [diff] [blame] | 145 | DEF_TEST(RTree, reporter) { |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 146 | SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN); |
| 147 | SkAutoUnref au(rtree); |
| 148 | rtree_test_main(rtree, reporter); |
| 149 | |
| 150 | // Rtree that orders input rectangles on deferred insert. |
sglez@google.com | ffb71f2 | 2013-08-30 17:43:31 +0000 | [diff] [blame] | 151 | SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false); |
| 152 | SkAutoUnref auo(unsortedRtree); |
| 153 | rtree_test_main(unsortedRtree, reporter); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 154 | } |