simplify rtree loops in Skia too
Sorry for yanking you around on whether on not this is worth doing.
Seems like SkRTrees are going to stick around for now for Flutter,
so I think we might as well keep both implementations up to date.
This ripples out a little further than in Chromium, as the math we're
deleting here was the only use of the aspect ratio of the passed-in
bounds, that itself the only use of those bounds themselves. So we can
un-plumb all that too. I'd still like to see how much we can minimize
the need for those user-provided bounds at all, especially when we're
calculating them all here.
Change-Id: Iea07e8e3d23a4dd31da8bcde512b24caabc96a10
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/213840
Reviewed-by: James Bankoski <jimbankoski@google.com>
Commit-Queue: Mike Klein <mtklein@google.com>
diff --git a/include/core/SkBBHFactory.h b/include/core/SkBBHFactory.h
index 78263eb..afd223f 100644
--- a/include/core/SkBBHFactory.h
+++ b/include/core/SkBBHFactory.h
@@ -17,13 +17,13 @@
/**
* Allocate a new SkBBoxHierarchy. Return NULL on failure.
*/
- virtual SkBBoxHierarchy* operator()(const SkRect& bounds) const = 0;
+ virtual SkBBoxHierarchy* operator()() const = 0;
virtual ~SkBBHFactory() {}
};
class SK_API SkRTreeFactory : public SkBBHFactory {
public:
- SkBBoxHierarchy* operator()(const SkRect& bounds) const override;
+ SkBBoxHierarchy* operator()() const override;
private:
typedef SkBBHFactory INHERITED;
};
diff --git a/src/core/SkBBHFactory.cpp b/src/core/SkBBHFactory.cpp
index 2d39a60..b4b0918 100644
--- a/src/core/SkBBHFactory.cpp
+++ b/src/core/SkBBHFactory.cpp
@@ -10,7 +10,6 @@
#include "include/core/SkScalar.h"
#include "src/core/SkRTree.h"
-SkBBoxHierarchy* SkRTreeFactory::operator()(const SkRect& bounds) const {
- SkScalar aspectRatio = bounds.width() / bounds.height();
- return new SkRTree(aspectRatio);
+SkBBoxHierarchy* SkRTreeFactory::operator()() const {
+ return new SkRTree;
}
diff --git a/src/core/SkPictureRecorder.cpp b/src/core/SkPictureRecorder.cpp
index 6391792..1fb23b8 100644
--- a/src/core/SkPictureRecorder.cpp
+++ b/src/core/SkPictureRecorder.cpp
@@ -32,7 +32,7 @@
fFlags = recordFlags;
if (bbhFactory) {
- fBBH.reset((*bbhFactory)(cullRect));
+ fBBH.reset((*bbhFactory)());
SkASSERT(fBBH.get());
}
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 7d44b1e..5688350 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -7,8 +7,7 @@
#include "src/core/SkRTree.h"
-SkRTree::SkRTree(SkScalar aspectRatio)
- : fCount(0), fAspectRatio(isfinite(aspectRatio) ? aspectRatio : 1) {}
+SkRTree::SkRTree() : fCount(0) {}
SkRect SkRTree::getRootBound() const {
if (fCount) {
@@ -45,7 +44,7 @@
fRoot.fSubtree = n;
fRoot.fBounds = branches[0].fBounds;
} else {
- fNodes.setReserve(CountNodes(fCount, fAspectRatio));
+ fNodes.setReserve(CountNodes(fCount));
fRoot = this->bulkLoad(&branches);
}
}
@@ -61,7 +60,7 @@
}
// This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
-int SkRTree::CountNodes(int branches, SkScalar aspectRatio) {
+int SkRTree::CountNodes(int branches) {
if (branches == 1) {
return 1;
}
@@ -75,30 +74,26 @@
remainder = kMinChildren - remainder;
}
}
- int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio));
- int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
int currentBranch = 0;
int nodes = 0;
- for (int i = 0; i < numStrips; ++i) {
- for (int j = 0; j < numTiles && currentBranch < branches; ++j) {
- int incrementBy = kMaxChildren;
- if (remainder != 0) {
- if (remainder <= kMaxChildren - kMinChildren) {
- incrementBy -= remainder;
- remainder = 0;
- } else {
- incrementBy = kMinChildren;
- remainder -= kMaxChildren - kMinChildren;
- }
- }
- nodes++;
- currentBranch++;
- for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
- currentBranch++;
+ while (currentBranch < branches) {
+ int incrementBy = kMaxChildren;
+ if (remainder != 0) {
+ if (remainder <= kMaxChildren - kMinChildren) {
+ incrementBy -= remainder;
+ remainder = 0;
+ } else {
+ incrementBy = kMinChildren;
+ remainder -= kMaxChildren - kMinChildren;
}
}
+ nodes++;
+ currentBranch++;
+ for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
+ currentBranch++;
+ }
}
- return nodes + CountNodes(nodes, aspectRatio);
+ return nodes + CountNodes(nodes);
}
SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
@@ -123,40 +118,34 @@
}
}
- int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
- int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
int currentBranch = 0;
-
- for (int i = 0; i < numStrips; ++i) {
- // Might be worth sorting by X here too.
- for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
- int incrementBy = kMaxChildren;
- if (remainder != 0) {
- // if need be, omit some nodes to make up for remainder
- if (remainder <= kMaxChildren - kMinChildren) {
- incrementBy -= remainder;
- remainder = 0;
- } else {
- incrementBy = kMinChildren;
- remainder -= kMaxChildren - kMinChildren;
- }
+ while (currentBranch < branches->count()) {
+ int incrementBy = kMaxChildren;
+ if (remainder != 0) {
+ // if need be, omit some nodes to make up for remainder
+ if (remainder <= kMaxChildren - kMinChildren) {
+ incrementBy -= remainder;
+ remainder = 0;
+ } else {
+ incrementBy = kMinChildren;
+ remainder -= kMaxChildren - kMinChildren;
}
- Node* n = allocateNodeAtLevel(level);
- n->fNumChildren = 1;
- n->fChildren[0] = (*branches)[currentBranch];
- Branch b;
- b.fBounds = (*branches)[currentBranch].fBounds;
- b.fSubtree = n;
- ++currentBranch;
- for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
- b.fBounds.join((*branches)[currentBranch].fBounds);
- n->fChildren[k] = (*branches)[currentBranch];
- ++n->fNumChildren;
- ++currentBranch;
- }
- (*branches)[newBranches] = b;
- ++newBranches;
}
+ Node* n = allocateNodeAtLevel(level);
+ n->fNumChildren = 1;
+ n->fChildren[0] = (*branches)[currentBranch];
+ Branch b;
+ b.fBounds = (*branches)[currentBranch].fBounds;
+ b.fSubtree = n;
+ ++currentBranch;
+ for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
+ b.fBounds.join((*branches)[currentBranch].fBounds);
+ n->fChildren[k] = (*branches)[currentBranch];
+ ++n->fNumChildren;
+ ++currentBranch;
+ }
+ (*branches)[newBranches] = b;
+ ++newBranches;
}
branches->setCount(newBranches);
return this->bulkLoad(branches, level + 1);
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index cdb2b50..021a58b 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -30,14 +30,7 @@
*/
class SkRTree : public SkBBoxHierarchy {
public:
-
-
- /**
- * If you have some prior information about the distribution of bounds you're expecting, you
- * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
- * create better proportioned tiles of rectangles.
- */
- explicit SkRTree(SkScalar aspectRatio = 1);
+ SkRTree();
~SkRTree() override {}
void insert(const SkRect[], int N) override;
@@ -81,13 +74,12 @@
Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
// How many times will bulkLoad() call allocateNodeAtLevel()?
- static int CountNodes(int branches, SkScalar aspectRatio);
+ static int CountNodes(int branches);
Node* allocateNodeAtLevel(uint16_t level);
// This is the count of data elements (rather than total nodes in the tree)
int fCount;
- SkScalar fAspectRatio;
Branch fRoot;
SkTDArray<Node> fNodes;
diff --git a/tests/PictureBBHTest.cpp b/tests/PictureBBHTest.cpp
index c80eee5..7c07c1f 100644
--- a/tests/PictureBBHTest.cpp
+++ b/tests/PictureBBHTest.cpp
@@ -94,18 +94,6 @@
emptyClipPictureTest.run(reporter);
}
-DEF_TEST(RTreeMakeLargest, r) {
- // A call to insert() with 2 or more rects and a bounds of SkRect::MakeLargest()
- // used to fall into an infinite loop.
-
- SkRTreeFactory factory;
- std::unique_ptr<SkBBoxHierarchy> bbh{ factory(SkRectPriv::MakeLargest()) };
-
- SkRect rects[] = { {0,0, 10,10}, {5,5,15,15} };
- bbh->insert(rects, SK_ARRAY_COUNT(rects));
- REPORTER_ASSERT(r, bbh->getRootBound() == SkRect::MakeWH(15,15));
-}
-
DEF_TEST(PictureNegativeSpace, r) {
SkRTreeFactory factory;
SkPictureRecorder recorder;
diff --git a/tests/PictureTest.cpp b/tests/PictureTest.cpp
index 44da230..81a929c 100644
--- a/tests/PictureTest.cpp
+++ b/tests/PictureTest.cpp
@@ -684,7 +684,7 @@
class SpoonFedBBHFactory : public SkBBHFactory {
public:
explicit SpoonFedBBHFactory(SkBBoxHierarchy* bbh) : fBBH(bbh) {}
- SkBBoxHierarchy* operator()(const SkRect&) const override {
+ SkBBoxHierarchy* operator()() const override {
return SkRef(fBBH);
}
private:
