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
random_rect(SkRandom & rand)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
random_data_rects(SkRandom & rand,DataRect out[],int n)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
verify_query(SkIRect query,DataRect rects[],SkTDArray<void * > & found)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
run_queries(skiatest::Reporter * reporter,SkRandom & rand,DataRect rects[],SkBBoxHierarchy & tree)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
tree_test_main(SkBBoxHierarchy * tree,int minChildren,int maxChildren,skiatest::Reporter * reporter)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
DEF_TEST(BBoxHierarchy,reporter)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