src/third_party/skia/tests/BBoxHierarchyTest.cpp

   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 "SkRTree.h"
  11 #include "SkTSort.h"
  12
  13 static const size_t RTREE_MIN_CHILDREN = 6;
  14 static const size_t RTREE_MAX_CHILDREN = 11;
  15
  16 static const int NUM_RECTS = 200;
  17 static const size_t NUM_ITERATIONS = 100;
  18 static const size_t NUM_QUERIES = 50;
  19
  20 static const SkScalar MAX_SIZE = 1000.0f;
  21
  22 struct DataRect {
  23     SkRect rect;
  24     void* data;
  25 };
  26
  27 static SkRect random_rect(SkRandom& rand) {
  28     SkRect rect = {0,0,0,0};
  29     while (rect.isEmpty()) {
  30         rect.fLeft   = rand.nextRangeF(0, MAX_SIZE);
  31         rect.fRight  = rand.nextRangeF(0, MAX_SIZE);
  32         rect.fTop    = rand.nextRangeF(0, MAX_SIZE);
  33         rect.fBottom = rand.nextRangeF(0, MAX_SIZE);
  34         rect.sort();
  35     }
  36     return rect;
  37 }
  38
  39 static void random_data_rects(SkRandom& rand, DataRect out[], int n) {
  40     for (int i = 0; i < n; ++i) {
  41         out[i].rect = random_rect(rand);
  42         out[i].data = reinterpret_cast<void*>(i);
  43     }
  44 }
  45
  46 static bool verify_query(SkRect query, DataRect rects[],
  47                          SkTDArray<void*>& found) {
  48     // TODO(mtklein): no need to do this after everything's SkRects
  49     query.roundOut();
  50
  51     SkTDArray<void*> expected;
  52     // manually intersect with every rectangle
  53     for (int i = 0; i < NUM_RECTS; ++i) {
  54         if (SkRect::Intersects(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         SkRect 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, 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 }