OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "Test.h" | 8 #include "Test.h" |
9 #include "SkRandom.h" | 9 #include "SkRandom.h" |
10 #include "SkRTree.h" | 10 #include "SkRTree.h" |
11 #include "SkTSort.h" | 11 #include "SkTSort.h" |
12 | 12 |
13 static const size_t RTREE_MIN_CHILDREN = 6; | 13 static const size_t RTREE_MIN_CHILDREN = 6; |
14 static const size_t RTREE_MAX_CHILDREN = 11; | 14 static const size_t RTREE_MAX_CHILDREN = 11; |
15 | 15 |
16 static const int NUM_RECTS = 200; | 16 static const int NUM_RECTS = 200; |
17 static const size_t NUM_ITERATIONS = 100; | 17 static const size_t NUM_ITERATIONS = 100; |
18 static const size_t NUM_QUERIES = 50; | 18 static const size_t NUM_QUERIES = 50; |
19 | 19 |
20 static const int MAX_SIZE = 1000; | 20 static const SkScalar MAX_SIZE = 1000.0f; |
21 | 21 |
22 struct DataRect { | 22 struct DataRect { |
23 SkIRect rect; | 23 SkRect rect; |
24 void* data; | 24 void* data; |
25 }; | 25 }; |
26 | 26 |
27 static SkIRect random_rect(SkRandom& rand) { | 27 static SkRect random_rect(SkRandom& rand) { |
28 SkIRect rect = {0,0,0,0}; | 28 SkRect rect = {0,0,0,0}; |
29 while (rect.isEmpty()) { | 29 while (rect.isEmpty()) { |
30 rect.fLeft = rand.nextS() % MAX_SIZE; | 30 rect.fLeft = rand.nextRangeF(0, MAX_SIZE); |
31 rect.fRight = rand.nextS() % MAX_SIZE; | 31 rect.fRight = rand.nextRangeF(0, MAX_SIZE); |
32 rect.fTop = rand.nextS() % MAX_SIZE; | 32 rect.fTop = rand.nextRangeF(0, MAX_SIZE); |
33 rect.fBottom = rand.nextS() % MAX_SIZE; | 33 rect.fBottom = rand.nextRangeF(0, MAX_SIZE); |
34 rect.sort(); | 34 rect.sort(); |
35 } | 35 } |
36 return rect; | 36 return rect; |
37 } | 37 } |
38 | 38 |
39 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { | 39 static void random_data_rects(SkRandom& rand, DataRect out[], int n) { |
40 for (int i = 0; i < n; ++i) { | 40 for (int i = 0; i < n; ++i) { |
41 out[i].rect = random_rect(rand); | 41 out[i].rect = random_rect(rand); |
42 out[i].data = reinterpret_cast<void*>(i); | 42 out[i].data = reinterpret_cast<void*>(i); |
43 } | 43 } |
44 } | 44 } |
45 | 45 |
46 static bool verify_query(SkIRect query, DataRect rects[], | 46 static bool verify_query(SkRect query, DataRect rects[], |
47 SkTDArray<void*>& found) { | 47 SkTDArray<void*>& found) { |
| 48 // TODO(mtklein): no need to do this after everything's SkRects |
| 49 query.roundOut(); |
| 50 |
48 SkTDArray<void*> expected; | 51 SkTDArray<void*> expected; |
49 // manually intersect with every rectangle | 52 // manually intersect with every rectangle |
50 for (int i = 0; i < NUM_RECTS; ++i) { | 53 for (int i = 0; i < NUM_RECTS; ++i) { |
51 if (SkIRect::IntersectsNoEmptyCheck(query, rects[i].rect)) { | 54 if (SkRect::Intersects(query, rects[i].rect)) { |
52 expected.push(rects[i].data); | 55 expected.push(rects[i].data); |
53 } | 56 } |
54 } | 57 } |
55 | 58 |
56 if (expected.count() != found.count()) { | 59 if (expected.count() != found.count()) { |
57 return false; | 60 return false; |
58 } | 61 } |
59 | 62 |
60 if (0 == expected.count()) { | 63 if (0 == expected.count()) { |
61 return true; | 64 return true; |
62 } | 65 } |
63 | 66 |
64 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... | 67 // Just cast to long since sorting by the value of the void*'s was being pro
blematic... |
65 SkTQSort(reinterpret_cast<long*>(expected.begin()), | 68 SkTQSort(reinterpret_cast<long*>(expected.begin()), |
66 reinterpret_cast<long*>(expected.end() - 1)); | 69 reinterpret_cast<long*>(expected.end() - 1)); |
67 SkTQSort(reinterpret_cast<long*>(found.begin()), | 70 SkTQSort(reinterpret_cast<long*>(found.begin()), |
68 reinterpret_cast<long*>(found.end() - 1)); | 71 reinterpret_cast<long*>(found.end() - 1)); |
69 return found == expected; | 72 return found == expected; |
70 } | 73 } |
71 | 74 |
72 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], | 75 static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, DataRect r
ects[], |
73 SkBBoxHierarchy& tree) { | 76 SkBBoxHierarchy& tree) { |
74 for (size_t i = 0; i < NUM_QUERIES; ++i) { | 77 for (size_t i = 0; i < NUM_QUERIES; ++i) { |
75 SkTDArray<void*> hits; | 78 SkTDArray<void*> hits; |
76 SkIRect query = random_rect(rand); | 79 SkRect query = random_rect(rand); |
77 tree.search(query, &hits); | 80 tree.search(query, &hits); |
78 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); | 81 REPORTER_ASSERT(reporter, verify_query(query, rects, hits)); |
79 } | 82 } |
80 } | 83 } |
81 | 84 |
82 static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildr
en, | 85 static void tree_test_main(SkBBoxHierarchy* tree, int minChildren, int maxChildr
en, |
83 skiatest::Reporter* reporter) { | 86 skiatest::Reporter* reporter) { |
84 DataRect rects[NUM_RECTS]; | 87 DataRect rects[NUM_RECTS]; |
85 SkRandom rand; | 88 SkRandom rand; |
86 REPORTER_ASSERT(reporter, NULL != tree); | 89 REPORTER_ASSERT(reporter, NULL != tree); |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
158 SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN)
; | 161 SkRTree* rtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN)
; |
159 SkAutoUnref au(rtree); | 162 SkAutoUnref au(rtree); |
160 tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter); | 163 tree_test_main(rtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, reporter); |
161 | 164 |
162 // Rtree that orders input rectangles on deferred insert. | 165 // Rtree that orders input rectangles on deferred insert. |
163 SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_C
HILDREN, 1, false); | 166 SkRTree* unsortedRtree = SkRTree::Create(RTREE_MIN_CHILDREN, RTREE_MAX_C
HILDREN, 1, false); |
164 SkAutoUnref auo(unsortedRtree); | 167 SkAutoUnref auo(unsortedRtree); |
165 tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, re
porter); | 168 tree_test_main(unsortedRtree, RTREE_MIN_CHILDREN, RTREE_MAX_CHILDREN, re
porter); |
166 } | 169 } |
167 } | 170 } |
OLD | NEW |