Home | History | Annotate | Download | only in tests 
      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 }
    171