Initial QuadTree implementation

In an effort to find a faster bounding box hierarchy than the R-Tree, a QuadTree has been implemented here.
For now, the QuadTree construction is generally faster than the R-Tree and the queries are a bit slower, so overall, SKP local tests showed QuadTree performance similar to the R-Tree performance.

Tests and bench are included in this cl.

At this point, I'd like to be able to commit this in order to more easily use the bots to test multiple configurations and a larger number of SKPs. The R-Tree BBH is still used by default so this change shouldn't affect chromium.

BUG=skia:
R=junov@chromium.org, junov@google.com, senorblanco@google.com, senorblanco@chromium.org, reed@google.com, sugoi@google.com, fmalita@google.com

Author: sugoi@chromium.org

Review URL: https://codereview.chromium.org/131343011

git-svn-id: http://skia.googlecode.com/svn/trunk@13282 2bbb7eff-a529-9590-31e7-b0007b416f81

7 files changed, 373 insertions, 7 deletions

diff --git a/src/core/SkBBoxHierarchy.h b/src/core/SkBBoxHierarchy.h
index 62b22d80e6..36047b9706 100644
--- a/src/core/SkBBoxHierarchy.h
+++ b/src/core/SkBBoxHierarchy.h
@@ -64,11 +64,21 @@ public:
     virtual void clear() = 0;
 
     /**
-     * Gets the number of insertions
+     * Gets the number of insertions actually made (does not include deferred insertions)
      */
     virtual int getCount() const = 0;
 
     /**
+     * Returns the depth of the currently allocated tree. The root node counts for 1 level,
+     * so it should be 1 or more if there's a root node. This information provides details
+     * about the underlying structure, which is useful mainly for testing purposes.
+     *
+     * Returns 0 if there are currently no nodes in the tree.
+     * Returns -1 if the structure isn't a tree.
+     */
+    virtual int getDepth() const = 0;
+
+    /**
      * Rewinds all the most recently inserted data elements until an element
      * is encountered for which client->shouldRewind(data) returns false. May
      * not rewind elements that were inserted prior to the last call to
diff --git a/src/core/SkQuadTree.cpp b/src/core/SkQuadTree.cpp
new file mode 100644
index 0000000000..c6ed4bf2e4
--- /dev/null
+++ b/src/core/SkQuadTree.cpp
@@ -0,0 +1,224 @@
+/*
+ * 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;
+};
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+SkQuadTree* SkQuadTree::Create(const SkIRect& bounds) {
+    return new SkQuadTree(bounds);
+}
+
+SkQuadTree::SkQuadTree(const SkIRect& bounds)
+    : fCount(0)
+    , fRoot(SkNEW_ARGS(QuadTreeNode, (bounds))) {
+    SkASSERT((bounds.width() * bounds.height()) > 0);
+}
+
+SkQuadTree::~SkQuadTree() {
+}
+
+void SkQuadTree::insert(void* data, const SkIRect& bounds, bool) {
+    if (bounds.isEmpty()) {
+        SkASSERT(false);
+        return;
+    }
+
+    QuadTreeNode::Data quadTreeData(bounds, data);
+    fRoot->insert(quadTreeData);
+    ++fCount;
+}
+
+void SkQuadTree::search(const SkIRect& query, SkTDArray<void*>* results) {
+    SkASSERT(NULL != results);
+    fRoot->queryRange(query, results);
+}
+
+void SkQuadTree::clear() {
+    fCount = 0;
+    fRoot->clear();
+}
+
+int SkQuadTree::getDepth() const {
+    return fRoot->getDepth();
+}
+
+void SkQuadTree::rewindInserts() {
+    SkASSERT(fClient);
+    fRoot->rewindInserts(fClient);
+}
diff --git a/src/core/SkQuadTree.h b/src/core/SkQuadTree.h
new file mode 100644
index 0000000000..a261749609
--- /dev/null
+++ b/src/core/SkQuadTree.h
@@ -0,0 +1,80 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkQuadTree_DEFINED
+#define SkQuadTree_DEFINED
+
+#include "SkRect.h"
+#include "SkTDArray.h"
+#include "SkBBoxHierarchy.h"
+
+/**
+ * An QuadTree implementation. In short, it is a tree containing a hierarchy of bounding rectangles
+ * in which each internal node has exactly four children.
+ *
+ * For more details see:
+ *
+ * http://en.wikipedia.org/wiki/Quadtree
+ */
+class SkQuadTree : public SkBBoxHierarchy {
+public:
+    SK_DECLARE_INST_COUNT(SkQuadTree)
+
+    /**
+     * Create a new QuadTree
+     */
+    static SkQuadTree* Create(const SkIRect& bounds);
+    virtual ~SkQuadTree();
+
+    /**
+     * Insert a node, consisting of bounds and a data value into the tree, if we don't immediately
+     * need to use the tree; we may allow the insert to be deferred (this can allow us to bulk-load
+     * a large batch of nodes at once, which tends to be faster and produce a better tree).
+     *  @param data The data value
+     *  @param bounds The corresponding bounding box
+     *  @param defer Can this insert be deferred? (this may be ignored)
+     */
+    virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
+
+    /**
+     * If any inserts have been deferred, this will add them into the tree
+     */
+    virtual void flushDeferredInserts() SK_OVERRIDE {}
+
+    /**
+     * Given a query rectangle, populates the passed-in array with the elements it intersects
+     */
+    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
+
+    virtual void clear() SK_OVERRIDE;
+
+    /**
+     * Gets the depth of the tree structure
+     */
+    virtual int getDepth() const SK_OVERRIDE;
+
+    /**
+     * This gets the insertion count (rather than the node count)
+     */
+    virtual int getCount() const SK_OVERRIDE { return fCount; }
+
+    virtual void rewindInserts() SK_OVERRIDE;
+
+private:
+    class QuadTreeNode;
+
+    SkQuadTree(const SkIRect& bounds);
+
+    // This is the count of data elements (rather than total nodes in the tree)
+    int fCount;
+
+    QuadTreeNode* fRoot;
+
+    typedef SkBBoxHierarchy INHERITED;
+};
+
+#endif
diff --git a/src/core/SkQuadTreePicture.cpp b/src/core/SkQuadTreePicture.cpp
new file mode 100644
index 0000000000..d05e40f4b3
--- /dev/null
+++ b/src/core/SkQuadTreePicture.cpp
@@ -0,0 +1,15 @@
+/*
+ * 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 "SkQuadTreePicture.h"
+
+#include "SkQuadTree.h"
+
+SkBBoxHierarchy* SkQuadTreePicture::createBBoxHierarchy() const {
+    return SkQuadTree::Create(fBounds);
+}
+
diff --git a/src/core/SkQuadTreePicture.h b/src/core/SkQuadTreePicture.h
new file mode 100644
index 0000000000..0427b394a0
--- /dev/null
+++ b/src/core/SkQuadTreePicture.h
@@ -0,0 +1,29 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkQuadTreePicture_DEFINED
+#define SkQuadTreePicture_DEFINED
+
+#include "SkPicture.h"
+#include "SkRect.h"
+
+/**
+ * Subclass of SkPicture that override the behavior of the
+ * kOptimizeForClippedPlayback_RecordingFlag by creating an SkQuadGrid
+ * structure rather than an R-Tree. The quad tree has generally faster
+ * tree creation time, but slightly slower query times, as compared to
+ * R-Tree, so some cases may be faster and some cases slower.
+ */
+class SK_API SkQuadTreePicture : public SkPicture {
+public:
+    SkQuadTreePicture(const SkIRect& bounds) : fBounds(bounds) {}
+    virtual SkBBoxHierarchy* createBBoxHierarchy() const SK_OVERRIDE;
+private:
+    SkIRect fBounds;
+};
+
+#endif
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 2f905e7909..d21b5f8d37 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -67,26 +67,32 @@ public:
      *  @param bounds The corresponding bounding box
      *  @param defer Can this insert be deferred? (this may be ignored)
      */
-    virtual void insert(void* data, const SkIRect& bounds, bool defer = false);
+    virtual void insert(void* data, const SkIRect& bounds, bool defer = false) SK_OVERRIDE;
 
     /**
      * If any inserts have been deferred, this will add them into the tree
      */
-    virtual void flushDeferredInserts();
+    virtual void flushDeferredInserts() SK_OVERRIDE;
 
     /**
      * Given a query rectangle, populates the passed-in array with the elements it intersects
      */
-    virtual void search(const SkIRect& query, SkTDArray<void*>* results);
+    virtual void search(const SkIRect& query, SkTDArray<void*>* results) SK_OVERRIDE;
 
-    virtual void clear();
+    virtual void clear() SK_OVERRIDE;
     bool isEmpty() const { return 0 == fCount; }
-    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+
+    /**
+     * Gets the depth of the tree structure
+     */
+    virtual int getDepth() const SK_OVERRIDE {
+        return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1;
+    }
 
     /**
      * This gets the insertion count (rather than the node count)
      */
-    virtual int getCount() const { return fCount; }
+    virtual int getCount() const SK_OVERRIDE { return fCount; }
 
     virtual void rewindInserts() SK_OVERRIDE;
 
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index bf3f6cfe02..c64a0289aa 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -63,6 +63,8 @@ public:
      */
     virtual int getCount() const SK_OVERRIDE;
 
+    virtual int getDepth() const SK_OVERRIDE { return -1; }
+
     virtual void rewindInserts() SK_OVERRIDE;
 
     // Used by search() and in SkTileGridHelper implementations