diff options
| author |  commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-02-03 18:08:33 +0000 |
|---|---|---|
| committer | commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-02-03 18:08:33 +0000 |
| commit | c22d1398089fdb95480fb3459b23e4931e4f5280 (patch) | |
| tree | a349b7c51fc610e7ed5ee2613220407f83ff009d /src/core/SkBBoxHierarchy.h | |
| parent | c048afc3df31d042800f9e13600da0017cc7a333 (diff) | |
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
Diffstat (limited to 'src/core/SkBBoxHierarchy.h')
| -rw-r--r-- | src/core/SkBBoxHierarchy.h | 12 |
1 files changed, 11 insertions, 1 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 |