Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(343)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: src/core/SkQuadTree.cpp

Issue 196383026: Slightly faster quadtree searching (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Remove commented out code Created 6 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/core/SkQuadTree.h ('k') | src/core/SkTObjectPool.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/core/SkQuadTree.cpp
diff --git a/src/core/SkQuadTree.cpp b/src/core/SkQuadTree.cpp
index 8531823278b111b29d9f7beef8029236a9500e29..3fd529de68685525491949cfb9991a10fa0e2104 100644
--- a/src/core/SkQuadTree.cpp
+++ b/src/core/SkQuadTree.cpp
@@ -11,67 +11,81 @@
#include <vector>
static const int kSplitThreshold = 8;
-static const int kMinDimensions = 128;
+
+enum {
+ kTopLeft,
+ kTopRight,
+ kBottomLeft,
+ kBottomRight,
+};
robertphillips 2014/03/17 13:26:52 kTopLeft_Bit, etc.?
iancottrell 2014/03/17 13:49:36 Done.
+enum {
+ kTopLeftBit = 1 << kTopLeft,
+ kTopRightBit = 1 << kTopRight,
+ kBottomLeftBit = 1 << kBottomLeft,
+ kBottomRightBit = 1 << kBottomRight,
+};
+enum {
+ kMaskLeft = kTopLeftBit | kBottomLeftBit,
+ kMaskRight = kTopRightBit | kBottomRightBit,
+ kMaskTop = kTopLeftBit | kTopRightBit,
+ kMaskBottom = kBottomLeftBit | kBottomRightBit,
+};
+
robertphillips 2014/03/17 13:26:52 child_intersect
iancottrell 2014/03/17 13:49:36 Done.
+static int childIntersect(const SkIRect& query, const SkIPoint& split) {
+ // fast quadrant test
+ int intersect = 0xf;
+ if (query.fRight < split.fX) {
+ intersect &= ~kMaskRight;
+ } else if(query.fLeft >= split.fX) {
+ intersect &= ~kMaskLeft;
+ }
+ if (query.fBottom < split.fY) {
+ intersect &= ~kMaskBottom;
+ } else if(query.fTop >= split.fY) {
+ intersect &= ~kMaskTop;
+ }
+ return intersect;
+}
SkQuadTree::SkQuadTree(const SkIRect& bounds)
- : fEntryCount(0)
- , fRoot(NULL) {
+ : fRoot(NULL) {
SkASSERT((bounds.width() * bounds.height()) > 0);
- fRoot = fNodePool.acquire();
- fRoot->fBounds = bounds;
+ fRootBounds = bounds;
}
SkQuadTree::~SkQuadTree() {
}
-SkQuadTree::Node* SkQuadTree::pickChild(Node* node,
- const SkIRect& bounds) const {
- // is it entirely to the left?
- int index = 0;
- if (bounds.fRight < node->fSplitPoint.fX) {
- // Inside the left side
- } else if(bounds.fLeft >= node->fSplitPoint.fX) {
- // Inside the right side
- index |= 1;
- } else {
- // Not inside any children
- return NULL;
- }
- if (bounds.fBottom < node->fSplitPoint.fY) {
- // Inside the top side
- } else if(bounds.fTop >= node->fSplitPoint.fY) {
- // Inside the bottom side
- index |= 2;
- } else {
- // Not inside any children
- return NULL;
- }
- return node->fChildren[index];
-}
-
void SkQuadTree::insert(Node* node, Entry* entry) {
// does it belong in a child?
if (NULL != node->fChildren[0]) {
- Node* child = pickChild(node, entry->fBounds);
- if (NULL != child) {
- insert(child, entry);
- } else {
- node->fEntries.push(entry);
+ switch(childIntersect(entry->fBounds, node->fSplitPoint)) {
+ case kTopLeftBit:
robertphillips 2014/03/17 13:26:52 this-> on all inserts
iancottrell 2014/03/17 13:49:36 Done.
+ insert(node->fChildren[kTopLeft], entry);
+ return;
+ case kTopRightBit:
+ insert(node->fChildren[kTopRight], entry);
+ return;
+ case kBottomLeftBit:
+ insert(node->fChildren[kBottomLeft], entry);
+ return;
+ case kBottomRightBit:
+ insert(node->fChildren[kBottomRight], entry);
+ return;
+ default:
+ node->fEntries.push(entry);
+ return;
}
- return;
}
// No children yet, add to this node
node->fEntries.push(entry);
// should I split?
tomhudson 2014/03/17 13:27:32 Got rid of minimum size?
iancottrell 2014/03/17 13:49:36 Yes, turns out it has no benefit.
- if (node->fEntries.getCount() < kSplitThreshold) {
- return;
- }
-
- if ((node->fBounds.width() < kMinDimensions) ||
- (node->fBounds.height() < kMinDimensions)) {
- return;
+ if (node->fEntries.getCount() > kSplitThreshold) {
robertphillips 2014/03/17 13:26:52 this->split
iancottrell 2014/03/17 13:49:36 Done.
+ split(node);
}
+}
+void SkQuadTree::split(Node* node) {
// Build all the children
node->fSplitPoint = SkIPoint::Make(node->fBounds.centerX(),
node->fBounds.centerY());
@@ -109,33 +123,11 @@ void SkQuadTree::search(Node* node, const SkIRect& query,
if (NULL == node->fChildren[0]) {
return;
}
- // fast quadrant test
- bool left = true;
- bool right = true;
- if (query.fRight < node->fSplitPoint.fX) {
- right = false;
- } else if(query.fLeft >= node->fSplitPoint.fX) {
- left = false;
- }
- bool top = true;
- bool bottom = true;
- if (query.fBottom < node->fSplitPoint.fY) {
- bottom = false;
- } else if(query.fTop >= node->fSplitPoint.fY) {
- top = false;
- }
- // search all the active quadrants
- if (top && left) {
- search(node->fChildren[0], query, results);
- }
- if (top && right) {
- search(node->fChildren[1], query, results);
- }
- if (bottom && left) {
- search(node->fChildren[2], query, results);
- }
- if (bottom && right) {
- search(node->fChildren[3], query, results);
+ int intersect = childIntersect(query, node->fSplitPoint);
+ for(int index=0; index<kChildCount; ++index) {
+ if (intersect & (1 << index)) {
robertphillips 2014/03/17 13:26:52 this->
iancottrell 2014/03/17 13:49:36 Done.
+ search(node->fChildren[index], query, results);
+ }
}
}
@@ -155,7 +147,7 @@ void SkQuadTree::clear(Node* node) {
int SkQuadTree::getDepth(Node* node) const {
int maxDepth = 0;
robertphillips 2014/03/17 13:26:52 NULL != node
iancottrell 2014/03/17 13:49:36 Done.
- if (NULL != node->fChildren[0]) {
+ if (node != NULL) {
for(int index=0; index<kChildCount; ++index) {
maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
}
@@ -171,8 +163,7 @@ void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
Entry* entry = fEntryPool.acquire();
entry->fData = data;
entry->fBounds = bounds;
- ++fEntryCount;
- if (fRoot->fEntries.isEmpty() && (NULL == fRoot->fChildren[0])) {
+ if (NULL == fRoot) {
fDeferred.push(entry);
} else {
insert(fRoot, entry);
@@ -180,16 +171,19 @@ void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
}
void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
- SkASSERT(fDeferred.isEmpty());
+ SkASSERT(NULL != fRoot);
SkASSERT(NULL != results);
- if (SkIRect::Intersects(fRoot->fBounds, query)) {
+ if (SkIRect::Intersects(fRootBounds, query)) {
robertphillips 2014/03/17 13:26:52 this->
iancottrell 2014/03/17 13:49:36 Done.
search(fRoot, query, results);
}
}
void SkQuadTree::clear() {
- fEntryCount = 0;
- clear(fRoot);
+ if (NULL != fRoot) {
robertphillips 2014/03/17 13:26:52 this->INHERITED:: ?
iancottrell 2014/03/17 13:49:36 No need for INHERITED, this-> added
+ clear(fRoot);
+ fNodePool.release(fRoot);
+ fRoot = NULL;
+ }
}
int SkQuadTree::getDepth() const {
@@ -199,7 +193,7 @@ int SkQuadTree::getDepth() const {
void SkQuadTree::rewindInserts() {
SkASSERT(fClient);
// Currently only supports deferred inserts
- SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
+ SkASSERT(NULL == fRoot);
SkTInternalSList<Entry> entries;
entries.pushAll(&fDeferred);
while(!entries.isEmpty()) {
@@ -207,7 +201,6 @@ void SkQuadTree::rewindInserts() {
if (fClient->shouldRewind(entry->fData)) {
entry->fData = NULL;
fEntryPool.release(entry);
- --fEntryCount;
} else {
fDeferred.push(entry);
}
@@ -215,6 +208,10 @@ void SkQuadTree::rewindInserts() {
}
void SkQuadTree::flushDeferredInserts() {
+ if (NULL == fRoot) {
+ fRoot = fNodePool.acquire();
+ fRoot->fBounds = fRootBounds;
+ }
while(!fDeferred.isEmpty()) {
insert(fRoot, fDeferred.pop());
}
« no previous file with comments | « src/core/SkQuadTree.h ('k') | src/core/SkTObjectPool.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698