1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkQuadTree.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,221 @@
1.4 +/*
1.5 + * Copyright 2014 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +
1.11 +#include "SkQuadTree.h"
1.12 +#include "SkTSort.h"
1.13 +#include <stdio.h>
1.14 +#include <vector>
1.15 +
1.16 +static const int kSplitThreshold = 8;
1.17 +static const int kMinDimensions = 128;
1.18 +
1.19 +SkQuadTree::SkQuadTree(const SkIRect& bounds)
1.20 + : fEntryCount(0)
1.21 + , fRoot(NULL) {
1.22 + SkASSERT((bounds.width() * bounds.height()) > 0);
1.23 + fRoot = fNodePool.acquire();
1.24 + fRoot->fBounds = bounds;
1.25 +}
1.26 +
1.27 +SkQuadTree::~SkQuadTree() {
1.28 +}
1.29 +
1.30 +SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
1.31 + const SkIRect& bounds) const {
1.32 + // is it entirely to the left?
1.33 + int index = 0;
1.34 + if (bounds.fRight < node->fSplitPoint.fX) {
1.35 + // Inside the left side
1.36 + } else if(bounds.fLeft >= node->fSplitPoint.fX) {
1.37 + // Inside the right side
1.38 + index |= 1;
1.39 + } else {
1.40 + // Not inside any children
1.41 + return NULL;
1.42 + }
1.43 + if (bounds.fBottom < node->fSplitPoint.fY) {
1.44 + // Inside the top side
1.45 + } else if(bounds.fTop >= node->fSplitPoint.fY) {
1.46 + // Inside the bottom side
1.47 + index |= 2;
1.48 + } else {
1.49 + // Not inside any children
1.50 + return NULL;
1.51 + }
1.52 + return node->fChildren[index];
1.53 +}
1.54 +
1.55 +void SkQuadTree::insert(Node* node, Entry* entry) {
1.56 + // does it belong in a child?
1.57 + if (NULL != node->fChildren[0]) {
1.58 + Node* child = pickChild(node, entry->fBounds);
1.59 + if (NULL != child) {
1.60 + insert(child, entry);
1.61 + } else {
1.62 + node->fEntries.push(entry);
1.63 + }
1.64 + return;
1.65 + }
1.66 + // No children yet, add to this node
1.67 + node->fEntries.push(entry);
1.68 + // should I split?
1.69 + if (node->fEntries.getCount() < kSplitThreshold) {
1.70 + return;
1.71 + }
1.72 +
1.73 + if ((node->fBounds.width() < kMinDimensions) ||
1.74 + (node->fBounds.height() < kMinDimensions)) {
1.75 + return;
1.76 + }
1.77 +
1.78 + // Build all the children
1.79 + node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
1.80 + node->fBounds.centerY());
1.81 + for(int index=0; index<kChildCount; ++index) {
1.82 + node->fChildren[index] = fNodePool.acquire();
1.83 + }
1.84 + node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
1.85 + node->fBounds.fLeft, node->fBounds.fTop,
1.86 + node->fSplitPoint.fX, node->fSplitPoint.fY);
1.87 + node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
1.88 + node->fSplitPoint.fX, node->fBounds.fTop,
1.89 + node->fBounds.fRight, node->fSplitPoint.fY);
1.90 + node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
1.91 + node->fBounds.fLeft, node->fSplitPoint.fY,
1.92 + node->fSplitPoint.fX, node->fBounds.fBottom);
1.93 + node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
1.94 + node->fSplitPoint.fX, node->fSplitPoint.fY,
1.95 + node->fBounds.fRight, node->fBounds.fBottom);
1.96 + // reinsert all the entries of this node to allow child trickle
1.97 + SkTInternalSList<Entry> entries;
1.98 + entries.pushAll(&node->fEntries);
1.99 + while(!entries.isEmpty()) {
1.100 + insert(node, entries.pop());
1.101 + }
1.102 +}
1.103 +
1.104 +void SkQuadTree::search(Node* node, const SkIRect& query,
1.105 + SkTDArray<void*>* results) const {
1.106 + for (Entry* entry = node->fEntries.head(); NULL != entry;
1.107 + entry = entry->getSListNext()) {
1.108 + if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
1.109 + results->push(entry->fData);
1.110 + }
1.111 + }
1.112 + if (NULL == node->fChildren[0]) {
1.113 + return;
1.114 + }
1.115 + // fast quadrant test
1.116 + bool left = true;
1.117 + bool right = true;
1.118 + if (query.fRight < node->fSplitPoint.fX) {
1.119 + right = false;
1.120 + } else if(query.fLeft >= node->fSplitPoint.fX) {
1.121 + left = false;
1.122 + }
1.123 + bool top = true;
1.124 + bool bottom = true;
1.125 + if (query.fBottom < node->fSplitPoint.fY) {
1.126 + bottom = false;
1.127 + } else if(query.fTop >= node->fSplitPoint.fY) {
1.128 + top = false;
1.129 + }
1.130 + // search all the active quadrants
1.131 + if (top && left) {
1.132 + search(node->fChildren[0], query, results);
1.133 + }
1.134 + if (top && right) {
1.135 + search(node->fChildren[1], query, results);
1.136 + }
1.137 + if (bottom && left) {
1.138 + search(node->fChildren[2], query, results);
1.139 + }
1.140 + if (bottom && right) {
1.141 + search(node->fChildren[3], query, results);
1.142 + }
1.143 +}
1.144 +
1.145 +void SkQuadTree::clear(Node* node) {
1.146 + // first clear the entries of this node
1.147 + fEntryPool.releaseAll(&node->fEntries);
1.148 + // recurse into and clear all child nodes
1.149 + for(int index=0; index<kChildCount; ++index) {
1.150 + Node* child = node->fChildren[index];
1.151 + node->fChildren[index] = NULL;
1.152 + if (NULL != child) {
1.153 + clear(child);
1.154 + fNodePool.release(child);
1.155 + }
1.156 + }
1.157 +}
1.158 +
1.159 +int SkQuadTree::getDepth(Node* node) const {
1.160 + int maxDepth = 0;
1.161 + if (NULL != node->fChildren[0]) {
1.162 + for(int index=0; index<kChildCount; ++index) {
1.163 + maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
1.164 + }
1.165 + }
1.166 + return maxDepth + 1;
1.167 +}
1.168 +
1.169 +void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
1.170 + if (bounds.isEmpty()) {
1.171 + SkASSERT(false);
1.172 + return;
1.173 + }
1.174 + Entry* entry = fEntryPool.acquire();
1.175 + entry->fData = data;
1.176 + entry->fBounds = bounds;
1.177 + ++fEntryCount;
1.178 + if (fRoot->fEntries.isEmpty() && (NULL == fRoot->fChildren[0])) {
1.179 + fDeferred.push(entry);
1.180 + } else {
1.181 + insert(fRoot, entry);
1.182 + }
1.183 +}
1.184 +
1.185 +void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
1.186 + SkASSERT(fDeferred.isEmpty());
1.187 + SkASSERT(NULL != results);
1.188 + if (SkIRect::Intersects(fRoot->fBounds, query)) {
1.189 + search(fRoot, query, results);
1.190 + }
1.191 +}
1.192 +
1.193 +void SkQuadTree::clear() {
1.194 + fEntryCount = 0;
1.195 + clear(fRoot);
1.196 +}
1.197 +
1.198 +int SkQuadTree::getDepth() const {
1.199 + return getDepth(fRoot);
1.200 +}
1.201 +
1.202 +void SkQuadTree::rewindInserts() {
1.203 + SkASSERT(fClient);
1.204 + // Currently only supports deferred inserts
1.205 + SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
1.206 + SkTInternalSList<Entry> entries;
1.207 + entries.pushAll(&fDeferred);
1.208 + while(!entries.isEmpty()) {
1.209 + Entry* entry = entries.pop();
1.210 + if (fClient->shouldRewind(entry->fData)) {
1.211 + entry->fData = NULL;
1.212 + fEntryPool.release(entry);
1.213 + --fEntryCount;
1.214 + } else {
1.215 + fDeferred.push(entry);
1.216 + }
1.217 + }
1.218 +}
1.219 +
1.220 +void SkQuadTree::flushDeferredInserts() {
1.221 + while(!fDeferred.isEmpty()) {
1.222 + insert(fRoot, fDeferred.pop());
1.223 + }
1.224 +}
