OLD | NEW |
(Empty) | |
| 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 |
| 8 #include "Test.h" |
| 9 #include "SkRandom.h" |
| 10 #include "SkQuadTree.h" |
| 11 #include "SkRTree.h" |
| 12 #include "SkTSort.h" |
| 13 |
| 14 static const size_t RTREE_MIN_CHILDREN = 6; |
| 15 static const size_t RTREE_MAX_CHILDREN = 11; |
| 16 static const size_t QUADTREE_MIN_CHILDREN = 4; |
| 17 static const size_t QUADTREE_MAX_CHILDREN = 0; // No hard limit for quadtree |
| 18 |
| 19 static const int NUM_RECTS = 200; |
| 20 static const size_t NUM_ITERATIONS = 100; |
| 21 static const size_t NUM_QUERIES = 50; |
| 22 |
| 23 static const int MAX_SIZE = 1000; |
| 24 |
| 25 struct DataRect { |
| 26 SkIRect rect; |
| 27 void* data; |
| 28 }; |
| 29 |
| 30 static SkIRect random_rect(SkRandom& rand) { |
| 31 SkIRect rect = {0,0,0,0}; |
| 32 while (rect.isEmpty()) { |
| 33 rect.fLeft = rand.nextS() % MAX_SIZE; |
| 34 rect.fRight = rand.nextS() % MAX_SIZE; |
| 35 rect.fTop = rand.nextS() % MAX_SIZE; |
| 36 rect.fBottom = rand.nextS() % MAX_SIZE; |
| 37 rect.sort(); |
| 38 } |
| 39 return rect; |
| 40 } |
| 41 |
| 42 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
| 43 for (int i = 0; i < n; ++i) { |
| 44 out[i].rect = random_rect(rand); |
| 45 out[i].data = reinterpret_cast<void*>(i); |
| 46 } |
| 47 } |
| 48 |
| 49 static bool verify_query(SkIRect query, DataRect rects[], |
| 50 SkTDArray<void*>& found) { |
| 51 SkTDArray<void*> expected; |
| 52 // manually intersect with every rectangle |
| 53 for (int i = 0; i < NUM_RECTS; ++i) { |
| 54 if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) { |
| 55 expected.push(rects[i].data); |
| 56 } |
| 57 } |
| 58 |
| 59 if (expected.count() != found.count()) { |
| 60 return false; |
| 61 } |
| 62 |
| 63 if (0 == expected.count()) { |
| 64 return true; |
| 65 } |
| 66 |
| 67 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... |
| 68 SkTQSort(reinterpret_cast<long*>(expected.begin()), |
| 69 reinterpret_cast<long*>(expected.end() - 1)); |
| 70 SkTQSort(reinterpret_cast<long*>(found.begin()), |
| 71 reinterpret_cast<long*>(found.end() - 1)); |
| 72 return found == expected; |
| 73 } |
| 74 |
| 75 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], |
| 76 SkBBoxHierarchy& tree) { |
| 77 for (size_t i = 0; i < NUM_QUERIES; ++i) { |
| 78 SkTDArray<void*> hits; |
| 79 SkIRect query = random_rect(rand); |
| 80 tree.search(query, &hits); |
| 81 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
| 82 } |
| 83 } |
| 84 |
| 85 static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildr
en, |
| 86 skiatest::Reporter* reporter) { |
| 87 DataRect rects[NUM_RECTS]; |
| 88 SkRandom rand; |
| 89 REPORTER_ASSERT(reporter, NULL != tree); |
| 90 |
| 91 int expectedDepthMin = -1; |
| 92 int expectedDepthMax = -1; |
| 93 |
| 94 int tmp = NUM_RECTS; |
| 95 if (maxChildren > 0) { |
| 96 while (tmp > 0) { |
| 97 tmp -= static_cast<int>(pow(static_cast<double>(maxChildren), |
| 98 static_cast<double>(expectedDepthMin + 1))); |
| 99 ++expectedDepthMin; |
| 100 } |
| 101 } |
| 102 |
| 103 tmp = NUM_RECTS; |
| 104 if (minChildren > 0) { |
| 105 while (tmp > 0) { |
| 106 tmp -= static_cast<int>(pow(static_cast<double>(minChildren), |
| 107 static_cast<double>(expectedDepthMax + 1))); |
| 108 ++expectedDepthMax; |
| 109 } |
| 110 } |
| 111 |
| 112 for (size_t i = 0; i < NUM_ITERATIONS; ++i) { |
| 113 random_data_rects(rand, rects, NUM_RECTS); |
| 114 |
| 115 // First try bulk-loaded inserts |
| 116 for (int i = 0; i < NUM_RECTS; ++i) { |
| 117 tree->insert(rects[i].data, rects[i].rect, true); |
| 118 } |
| 119 tree->flushDeferredInserts(); |
| 120 run_queries(reporter, rand, rects, *tree); |
| 121 REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount()); |
| 122 REPORTER_ASSERT(reporter, |
| 123 ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth()))
&& |
| 124 ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())))
; |
| 125 tree->clear(); |
| 126 REPORTER_ASSERT(reporter, 0 == tree->getCount()); |
| 127 |
| 128 // Then try immediate inserts |
| 129 for (int i = 0; i < NUM_RECTS; ++i) { |
| 130 tree->insert(rects[i].data, rects[i].rect); |
| 131 } |
| 132 run_queries(reporter, rand, rects, *tree); |
| 133 REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount()); |
| 134 REPORTER_ASSERT(reporter, |
| 135 ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth()))
&& |
| 136 ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth())))
; |
| 137 tree->clear(); |
| 138 REPORTER_ASSERT(reporter, 0 == tree->getCount()); |
| 139 |
| 140 // And for good measure try immediate inserts, but in reversed order |
| 141 for (int i = NUM_RECTS - 1; i >= 0; --i) { |
| 142 tree->insert(rects[i].data, rects[i].rect); |
| 143 } |
| 144 run_queries(reporter, rand, rects, *tree); |
| 145 REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount()); |
| 146 REPORTER_ASSERT(reporter, |
| 147 ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) &
& |
| 148 ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth()))); |
| 149 tree->clear(); |
| 150 REPORTER_ASSERT(reporter, 0 == tree->getCount()); |
| 151 } |
| 152 } |
| 153 |
| 154 DEF_TEST(BBoxHierarchy, reporter) { |
| 155 // RTree |
| 156 { |
| 157 SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN)
; |
| 158 SkAutoUnref au(rtree); |
| 159 tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter); |
| 160 |
| 161 // Rtree that orders input rectangles on deferred insert. |
| 162 SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_C
HILDREN, 1, false); |
| 163 SkAutoUnref auo(unsortedRtree); |
| 164 tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, re
porter); |
| 165 } |
| 166 |
| 167 // QuadTree |
| 168 { |
| 169 SkQuadTree* quadtree = SkQuadTree::Create( |
| 170 SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)); |
| 171 SkAutoUnref au(quadtree); |
| 172 tree_test_main(quadtree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, r
eporter); |
| 173 |
| 174 // QuadTree that orders input rectangles on deferred insert. |
| 175 SkQuadTree* unsortedQuadTree = SkQuadTree::Create( |
| 176 SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE)); |
| 177 SkAutoUnref auo(unsortedQuadTree); |
| 178 tree_test_main(unsortedQuadTree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHI
LDREN, reporter); |
| 179 } |
| 180 } |
OLD | NEW |