Home | History | Annotate | Download | only in core 
      1 /*
      2  * Copyright 2014 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 "SkQuadTree.h"
      9 #include "SkTSort.h"
     10 #include <stdio.h>
     11 
     12 static const int kSplitThreshold = 8;
     13 
     14 enum {
     15     kTopLeft,
     16     kTopRight,
     17     kBottomLeft,
     18     kBottomRight,
     19 };
     20 enum {
     21     kTopLeft_Bit = 1 << kTopLeft,
     22     kTopRight_Bit = 1 << kTopRight,
     23     kBottomLeft_Bit = 1 << kBottomLeft,
     24     kBottomRight_Bit = 1 << kBottomRight,
     25 };
     26 enum {
     27     kMaskLeft = kTopLeft_Bit | kBottomLeft_Bit,
     28     kMaskRight = kTopRight_Bit | kBottomRight_Bit,
     29     kMaskTop = kTopLeft_Bit | kTopRight_Bit,
     30     kMaskBottom = kBottomLeft_Bit | kBottomRight_Bit,
     31 };
     32 
     33 static U8CPU child_intersect(const SkIRect& query, const SkIPoint& split) {
     34     // fast quadrant test
     35     U8CPU intersect = 0xf;
     36     if (query.fRight <  split.fX) {
     37         intersect &= ~kMaskRight;
     38     } else if(query.fLeft >= split.fX) {
     39         intersect &= ~kMaskLeft;
     40     }
     41     if (query.fBottom < split.fY) {
     42         intersect &= ~kMaskBottom;
     43     } else if(query.fTop >= split.fY) {
     44         intersect &= ~kMaskTop;
     45     }
     46     return intersect;
     47 }
     48 
     49 SkQuadTree::SkQuadTree(const SkIRect& bounds) : fRoot(NULL) {
     50     SkASSERT((bounds.width() * bounds.height()) > 0);
     51     fRootBounds = bounds;
     52 }
     53 
     54 SkQuadTree::~SkQuadTree() {
     55 }
     56 
     57 void SkQuadTree::insert(Node* node, Entry* entry) {
     58     // does it belong in a child?
     59     if (NULL != node->fChildren[0]) {
     60         switch(child_intersect(entry->fBounds, node->fSplitPoint)) {
     61             case kTopLeft_Bit:
     62                 this->insert(node->fChildren[kTopLeft], entry);
     63                 return;
     64             case kTopRight_Bit:
     65                 this->insert(node->fChildren[kTopRight], entry);
     66                 return;
     67             case kBottomLeft_Bit:
     68                 this->insert(node->fChildren[kBottomLeft], entry);
     69                 return;
     70             case kBottomRight_Bit:
     71                 this->insert(node->fChildren[kBottomRight], entry);
     72                 return;
     73             default:
     74                 node->fEntries.push(entry);
     75                 return;
     76         }
     77     }
     78     // No children yet, add to this node
     79     node->fEntries.push(entry);
     80     // should I split?
     81     if (node->fEntries.getCount() > kSplitThreshold) {
     82         this->split(node);
     83     }
     84 }
     85 
     86 void SkQuadTree::split(Node* node) {
     87     // Build all the children
     88     node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
     89                                        node->fBounds.centerY());
     90     for(int index=0; index<kChildCount; ++index) {
     91         node->fChildren[index] = fNodePool.acquire();
     92     }
     93     node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
     94         node->fBounds.fLeft,    node->fBounds.fTop,
     95         node->fSplitPoint.fX,   node->fSplitPoint.fY);
     96     node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
     97         node->fSplitPoint.fX,   node->fBounds.fTop,
     98         node->fBounds.fRight,   node->fSplitPoint.fY);
     99     node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
    100         node->fBounds.fLeft,    node->fSplitPoint.fY,
    101         node->fSplitPoint.fX,   node->fBounds.fBottom);
    102     node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
    103         node->fSplitPoint.fX,   node->fSplitPoint.fY,
    104         node->fBounds.fRight,   node->fBounds.fBottom);
    105     // reinsert all the entries of this node to allow child trickle
    106     SkTInternalSList<Entry> entries;
    107     entries.pushAll(&node->fEntries);
    108     while(!entries.isEmpty()) {
    109         this->insert(node, entries.pop());
    110     }
    111 }
    112 
    113 void SkQuadTree::search(Node* node, const SkIRect& query,
    114                         SkTDArray<void*>* results) const {
    115     for (Entry* entry = node->fEntries.head(); NULL != entry;
    116         entry = entry->getSListNext()) {
    117         if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
    118             results->push(entry->fData);
    119         }
    120     }
    121     if (NULL == node->fChildren[0]) {
    122         return;
    123     }
    124     U8CPU intersect = child_intersect(query, node->fSplitPoint);
    125     for(int index=0; index<kChildCount; ++index) {
    126         if (intersect & (1 << index)) {
    127             this->search(node->fChildren[index], query, results);
    128         }
    129     }
    130 }
    131 
    132 void SkQuadTree::clear(Node* node) {
    133     // first clear the entries of this node
    134     fEntryPool.releaseAll(&node->fEntries);
    135     // recurse into and clear all child nodes
    136     for(int index=0; index<kChildCount; ++index) {
    137         Node* child = node->fChildren[index];
    138         node->fChildren[index] = NULL;
    139         if (NULL != child) {
    140             this->clear(child);
    141             fNodePool.release(child);
    142         }
    143     }
    144 }
    145 
    146 int SkQuadTree::getDepth(Node* node) const {
    147     int maxDepth = 0;
    148     if (NULL != node) {
    149         for(int index=0; index<kChildCount; ++index) {
    150             maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
    151         }
    152     }
    153     return maxDepth + 1;
    154 }
    155 
    156 void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
    157     if (bounds.isEmpty()) {
    158         SkASSERT(false);
    159         return;
    160     }
    161     Entry* entry = fEntryPool.acquire();
    162     entry->fData = data;
    163     entry->fBounds = bounds;
    164     if (NULL == fRoot) {
    165         fDeferred.push(entry);
    166     } else {
    167         this->insert(fRoot, entry);
    168     }
    169 }
    170 
    171 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
    172     SkASSERT(NULL != fRoot);
    173     SkASSERT(NULL != results);
    174     if (SkIRect::Intersects(fRootBounds, query)) {
    175         this->search(fRoot, query, results);
    176     }
    177 }
    178 
    179 void SkQuadTree::clear() {
    180     this->flushDeferredInserts();
    181     if (NULL != fRoot) {
    182         this->clear(fRoot);
    183         fNodePool.release(fRoot);
    184         fRoot = NULL;
    185     }
    186     SkASSERT(fEntryPool.allocated() == fEntryPool.available());
    187     SkASSERT(fNodePool.allocated() == fNodePool.available());
    188 }
    189 
    190 int SkQuadTree::getDepth() const {
    191     return this->getDepth(fRoot);
    192 }
    193 
    194 void SkQuadTree::rewindInserts() {
    195     SkASSERT(fClient);
    196      // Currently only supports deferred inserts
    197     SkASSERT(NULL == fRoot);
    198     SkTInternalSList<Entry> entries;
    199     entries.pushAll(&fDeferred);
    200     while(!entries.isEmpty()) {
    201         Entry* entry = entries.pop();
    202         if (fClient->shouldRewind(entry->fData)) {
    203             entry->fData = NULL;
    204             fEntryPool.release(entry);
    205         } else {
    206             fDeferred.push(entry);
    207         }
    208     }
    209 }
    210 
    211 void SkQuadTree::flushDeferredInserts() {
    212     if (NULL == fRoot) {
    213         fRoot = fNodePool.acquire();
    214         fRoot->fBounds = fRootBounds;
    215     }
    216     while(!fDeferred.isEmpty()) {
    217         this->insert(fRoot, fDeferred.pop());
    218     }
    219 }
    220