Fast implementation of QuadTree

src/core/SkQuadTree.cpp

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkQuadTree.h"
 #include "SkTSort.h"
 #include <stdio.h>
 #include <vector>
 
-class SkQuadTree::QuadTreeNode {
-public:
-    struct Data {
-        Data(const SkIRect& bounds, void* data) : fBounds(bounds), fInnerBounds(bounds), fData(data) {}
-        SkIRect fBounds;
-        SkIRect fInnerBounds;
-        void* fData;
-    };
-
-    QuadTreeNode(const SkIRect& bounds)
-     : fBounds(bounds)
-     , fTopLeft(NULL)
-     , fTopRight(NULL)
-     , fBottomLeft(NULL)
-     , fBottomRight(NULL)
-     , fCanSubdivide((fBounds.width() * fBounds.height()) > 0) {}
-
-    ~QuadTreeNode() {
-        clear();
-    }
-
-    void clear() {
-        SkDELETE(fTopLeft);
-        fTopLeft = NULL;
-        SkDELETE(fTopRight);
-        fTopRight = NULL;
-        SkDELETE(fBottomLeft);
-        fBottomLeft = NULL;
-        SkDELETE(fBottomRight);
-        fBottomRight = NULL;
-        fData.reset();
-    }
-
-    const SkIRect& getBounds() const { return fBounds; }
-
-    // Insert data into the QuadTreeNode
-    bool insert(Data& data) {
-        // Ignore objects which do not belong in this quad tree
-        return data.fInnerBounds.intersect(fBounds) && doInsert(data);
-    }
-
-    // Find all data which appear within a range
-    void queryRange(const SkIRect& range, SkTDArray<void*>* dataInRange) const {
-        // Automatically abort if the range does not collide with this quad
-        if (!SkIRect::Intersects(fBounds, range)) {
-            return; // nothing added to the list
-        }
-
-        // Check objects at this quad level
-        for (int i = 0; i < fData.count(); ++i) {
-            if (SkIRect::Intersects(fData[i].fBounds, range)) {
-                dataInRange->push(fData[i].fData);
-            }
-        }
-
-        // Terminate here, if there are no children
-        if (!hasChildren()) {
-            return;
-        }
-
-        // Otherwise, add the data from the children
-        fTopLeft->queryRange(range, dataInRange);
-        fTopRight->queryRange(range, dataInRange);
-        fBottomLeft->queryRange(range, dataInRange);
-        fBottomRight->queryRange(range, dataInRange);
-    }
-
-    int getDepth(int i = 1) const {
-        if (hasChildren()) {
-            int depthTL = fTopLeft->getDepth(++i);
-            int depthTR = fTopRight->getDepth(i);
-            int depthBL = fBottomLeft->getDepth(i);
-            int depthBR = fBottomRight->getDepth(i);
-            return SkTMax(SkTMax(depthTL, depthTR), SkTMax(depthBL, depthBR));
-        }
-        return i;
-    }
-
-    void rewindInserts(SkBBoxHierarchyClient* client) {
-        for (int i = fData.count() - 1; i >= 0; --i) {
-            if (client->shouldRewind(fData[i].fData)) {
-                fData.remove(i);
-            }
-        }
-        if (hasChildren()) {
-            fTopLeft->rewindInserts(client);
-            fTopRight->rewindInserts(client);
-            fBottomLeft->rewindInserts(client);
-            fBottomRight->rewindInserts(client);
-        }
-    }
-
-private:
-    // create four children which fully divide this quad into four quads of equal area
-    void subdivide() {
-        if (!hasChildren() && fCanSubdivide) {
-            SkIPoint center = SkIPoint::Make(fBounds.centerX(), fBounds.centerY());
-            fTopLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
-                fBounds.fLeft, fBounds.fTop, center.fX, center.fY)));
-            fTopRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
-                center.fX, fBounds.fTop, fBounds.fRight, center.fY)));
-            fBottomLeft = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
-                fBounds.fLeft, center.fY, center.fX, fBounds.fBottom)));
-            fBottomRight = SkNEW_ARGS(QuadTreeNode, (SkIRect::MakeLTRB(
-                center.fX, center.fY, fBounds.fRight, fBounds.fBottom)));
-
-            // If any of the data can fit entirely into a subregion, move it down now
-            for (int i = fData.count() - 1; i >= 0; --i) {
-                // If the data fits entirely into one of the 4 subregions, move that data
-                // down to that subregion.
-                if (fTopLeft->doInsert(fData[i]) ||
-                    fTopRight->doInsert(fData[i]) ||
-                    fBottomLeft->doInsert(fData[i]) ||
-                    fBottomRight->doInsert(fData[i])) {
-                    fData.remove(i);
-                }
-            }
-        }
-    }
-
-    bool doInsert(const Data& data) {
-        if (!fBounds.contains(data.fInnerBounds)) {
-            return false;
-        }
-
-        if (fData.count() > kQuadTreeNodeCapacity) {
-            subdivide();
-        }
-
-        // If there is space in this quad tree, add the object here
-        // If this quadtree can't be subdivided, we have no choice but to add it here
-        if ((fData.count() <= kQuadTreeNodeCapacity) || !fCanSubdivide) {
-            if (fData.isEmpty()) {
-                fData.setReserve(kQuadTreeNodeCapacity);
-            }
-            fData.push(data);
-        } else if (!fTopLeft->doInsert(data) && !fTopRight->doInsert(data) &&
-                   !fBottomLeft->doInsert(data) && !fBottomRight->doInsert(data)) {
-            // Can't be pushed down to children ? keep it here
-            fData.push(data);
-        }
-
-        return true;
-    }
-
-    bool hasChildren() const {
-        return (NULL != fTopLeft);
-    }
-
-    // Arbitrary constant to indicate how many elements can be stored in this quad tree node
-    enum { kQuadTreeNodeCapacity = 4 };
-
-    // Bounds of this quad tree
-    SkIRect fBounds;
-
-    // Data in this quad tree node
-    SkTDArray<Data> fData;
-
-    // Children
-    QuadTreeNode* fTopLeft;
-    QuadTreeNode* fTopRight;
-    QuadTreeNode* fBottomLeft;
-    QuadTreeNode* fBottomRight;
-
-    // Whether or not this node can have children
-    bool fCanSubdivide;
-};
-
-///////////////////////////////////////////////////////////////////////////////////////////////////
+static const int kSplitThreshold = 8;
+static const int kMinDimensions = 128;
 
 SkQuadTree* SkQuadTree::Create(const SkIRect& bounds) {
     return new SkQuadTree(bounds);
 }
 
 SkQuadTree::SkQuadTree(const SkIRect& bounds)
-    : fCount(0)
-    , fRoot(SkNEW_ARGS(QuadTreeNode, (bounds))) {
+    : fEntryCount(0)
+    , fRoot(NULL) {
     SkASSERT((bounds.width() * bounds.height()) > 0);
+    fRoot = fAllNodes.pop();
+    fRoot->fBounds = bounds;
 }
 
 SkQuadTree::~SkQuadTree() {
-    SkDELETE(fRoot);
+}
+
+SkQuadTree::Node* SkQuadTree::pickChild(Node* node, const SkIRect& bounds) const {

[tomhudson, 2014/03/05 11:56:56]

IIRC in conversation you said you had support for using a QuadTree. Is it
somewhere? The more I think about webpage structures, the more I think about
text spans, which naively are going to tend to frequently cross the page
centerline and therefore be forced into the root node?

[iancottrell, 2014/03/05 12:11:16]

Yes, I worry that web pages might have common pathological structures where many
elements overlap the split points.
There are ways around this, QuadTree's don't *have* to be center point split,
and this implementation would deliberately allow it to not be. Non center point
splits are viable when doing bulk loads, where you can try to work out a good
split point because you have full information, normally you try to find a split
point that is close to the middle that cuts the fewest possible bounds. 
It is horribly complicated to write and understand, and would probably be much
slower at record time though, so unless this is doing such a bad job that we see
it in playback results, I don't think it is worth doing.

+    // is it entirely to the left?
+    int index = 0;
+    if (bounds.fRight < node->fCenter.fX) {
+        // Inside the left side
+    } else if(bounds.fLeft >= node->fCenter.fX) {
+        // Inside the right side
+        index |= 1;
+    } else {
+        // Not inside any children
+        return NULL;
+    }
+    if (bounds.fBottom < node->fCenter.fY) {
+        // Inside the top side
+    } else if(bounds.fTop >= node->fCenter.fY) {
+        // Inside the bottom side
+        index |= 2;
+    } else {
+        // Not inside any children
+        return NULL;
+    }
+    SkASSERT(node->fChildren[index]->fBounds.contains(bounds));
+    return node->fChildren[index];
+}
+
+void SkQuadTree::insert(Node* node, Entry* entry) {
+    // does it belong in a child?
+    if (node->fChildren[0] != NULL) {
+        Node* child = pickChild(node, entry->fBounds);
+        if (child != NULL) {
+            insert(child, entry);
+        } else {
+            node->fEntries.push(entry);
+        }
+        return;
+    }
+    // No children yet, add to this node
+    node->fEntries.push(entry);
+    // should I split?
+    if (node->fEntries.getCount() < kSplitThreshold) {
+        return;
+    }
+
+    if ((node->fBounds.width() < kMinDimensions) ||
+        (node->fBounds.height() < kMinDimensions)) {
+        return;
+    }
+
+    // Build all the children
+    node->fCenter = SkIPoint::Make(node->fBounds.centerX(), node->fBounds.centerY());
+    for(int index=0; index<kChildCount; ++index) {
+        node->fChildren[index] = fAllNodes.pop();
+    }
+    node->fChildren[0]->fBounds = SkIRect::MakeLTRB(
+        node->fBounds.fLeft,   node->fBounds.fTop,    node->fCenter.fX,      node->fCenter.fY);
+    node->fChildren[1]->fBounds = SkIRect::MakeLTRB(
+        node->fCenter.fX,      node->fBounds.fTop,    node->fBounds.fRight,  node->fCenter.fY);
+    node->fChildren[2]->fBounds = SkIRect::MakeLTRB(
+        node->fBounds.fLeft, node->fCenter.fY,        node->fCenter.fX,      node->fBounds.fBottom);
+    node->fChildren[3]->fBounds = SkIRect::MakeLTRB(
+        node->fCenter.fX,      node->fCenter.fY,      node->fBounds.fRight,  node->fBounds.fBottom);
+    // reinsert all the entries of this node to allow child trickle
+    SkSList<Entry> entries;
+    entries.takeAll(node->fEntries);
+    while(!entries.isEmpty()) {
+        insert(node, entries.pop());
+    }
+}
+
+void SkQuadTree::search(Node* node, const SkIRect& query, SkTDArray<void*>* results) const {
+    if (!SkIRect::IntersectsNoEmptyCheck(node->fBounds, query)) {
+        return; // nothing added to the list
+    }
+    for (Entry* entry = node->fEntries.head(); entry != NULL; entry = entry->fNext) {
+        if (SkIRect::IntersectsNoEmptyCheck(entry->fBounds, query)) {
+            results->push(entry->fData);
+        }
+    }
+    if (node->fChildren[0] != NULL) {
+        for(int index=0; index<kChildCount; ++index) {
+            search(node->fChildren[index], query, results);
+        }
+    }
+}
+
+void SkQuadTree::clear(Node* node) {
+    // first clear the entries of this node
+    fAllEntries.takeAll(node->fEntries);
+    // recurse into and clear all child nodes
+    for(int index=0; index<kChildCount; ++index) {
+        Node* child = node->fChildren[index];
+        node->fChildren[index] = NULL;
+        if (child != NULL) {
+            clear(child);
+            fAllNodes.push(child);
+        }
+    }
+}
+
+int SkQuadTree::getDepth(Node* node) const {
+    int maxDepth = 0;
+    if (node->fChildren[0] != NULL) {
+        for(int index=0; index<kChildCount; ++index) {
+            maxDepth = SkMax32(maxDepth, getDepth(node->fChildren[index]));
+        }
+    }
+    return maxDepth + 1;
 }
 
 void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
     if (bounds.isEmpty()) {
         SkASSERT(false);
         return;
     }
-
-    QuadTreeNode::Data quadTreeData(bounds, data);
-    fRoot->insert(quadTreeData);
-    ++fCount;
+    Entry* entry = fAllEntries.pop();
+    entry->fData = data;
+    entry->fBounds = bounds;
+    ++fEntryCount;
+    //if (fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL) {
+    //    fDeferred.push(entry);
+    //} else {
+        insert(fRoot, entry);
+    //}
 }
 
 void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
     SkASSERT(NULL != results);
-    fRoot->queryRange(query, results);
+    if (!query.isEmpty()) {
+        search(fRoot, query, results);
+    }
 }
 
 void SkQuadTree::clear() {
-    fCount = 0;
-    fRoot->clear();
+    fEntryCount = 0;
+    clear(fRoot);
 }
 
 int SkQuadTree::getDepth() const {
-    return fRoot->getDepth();
+    return getDepth(fRoot);
 }
 
 void SkQuadTree::rewindInserts() {
     SkASSERT(fClient);
-    fRoot->rewindInserts(fClient);
+     // Currently only supports deferred inserts
+    SkASSERT(fRoot->fEntries.isEmpty() && fRoot->fChildren[0] == NULL);
+    SkSList<Entry> entries;
+    entries.takeAll(fDeferred);
+    while(!entries.isEmpty()) {
+        Entry* entry = entries.pop();
+        if (fClient->shouldRewind(entry->fData)) {
+            entry->fData = NULL;
+            fAllEntries.push(entry);
+            --fEntryCount;
+        } else {
+            fDeferred.push(entry);
+        }
+    }
 }
+
+void SkQuadTree::flushDeferredInserts() {
+    while(!fDeferred.isEmpty()) {
+        insert(fRoot, fDeferred.pop());
+    }
+}