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 = 0; 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 problematic... 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 rects[], 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 maxChildren, 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 tree->insert(rects[0].data, rects[0].rect); 130 tree->flushDeferredInserts(); 131 for (int i = 1; i < NUM_RECTS; ++i) { 132 tree->insert(rects[i].data, rects[i].rect); 133 } 134 run_queries(reporter, rand, rects, *tree); 135 REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount()); 136 REPORTER_ASSERT(reporter, 137 ((expectedDepthMin <= 0) || (expectedDepthMin <= tree->getDepth())) && 138 ((expectedDepthMax <= 0) || (expectedDepthMax >= tree->getDepth()))); 139 tree->clear(); 140 REPORTER_ASSERT(reporter, 0 == tree->getCount()); 141 142 // And for good measure try immediate inserts, but in reversed order 143 tree->insert(rects[NUM_RECTS - 1].data, rects[NUM_RECTS - 1].rect); 144 tree->flushDeferredInserts(); 145 for (int i = NUM_RECTS - 2; i >= 0; --i) { 146 tree->insert(rects[i].data, rects[i].rect); 147 } 148 run_queries(reporter, rand, rects, *tree); 149 REPORTER_ASSERT(reporter, NUM_RECTS == tree->getCount()); 150 REPORTER_ASSERT(reporter, 151 ((expectedDepthMin < 0) || (expectedDepthMin <= tree->getDepth())) && 152 ((expectedDepthMax < 0) || (expectedDepthMax >= tree->getDepth()))); 153 tree->clear(); 154 REPORTER_ASSERT(reporter, 0 == tree->getCount()); 155 } 156 } 157 158 DEF_TEST(BBoxHierarchy, reporter) { 159 // RTree 160 { 161 SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN); 162 SkAutoUnref au(rtree); 163 tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter); 164 165 // Rtree that orders input rectangles on deferred insert. 166 SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, 1, false); 167 SkAutoUnref auo(unsortedRtree); 168 tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter); 169 } 170 171 // QuadTree 172 { 173 SkQuadTree* quadtree = SkNEW_ARGS(SkQuadTree, ( 174 SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE))); 175 SkAutoUnref au(quadtree); 176 tree_test_main(quadtree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter); 177 178 // QuadTree that orders input rectangles on deferred insert. 179 SkQuadTree* unsortedQuadTree = SkNEW_ARGS(SkQuadTree, ( 180 SkIRect::MakeLTRB(-MAX_SIZE, -MAX_SIZE, MAX_SIZE, MAX_SIZE))); 181 SkAutoUnref auo(unsortedQuadTree); 182 tree_test_main(unsortedQuadTree, QUADTREE_MIN_CHILDREN, QUADTREE_MAX_CHILDREN, reporter); 183 } 184 } 185
