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
diff --git a/samplecode/SamplePictFile.cpp b/samplecode/SamplePictFile.cpp
index c6518d9..5cd16bd 100644
--- a/samplecode/SamplePictFile.cpp
+++ b/samplecode/SamplePictFile.cpp
@@ -15,6 +15,7 @@
#include "SkOSFile.h"
#include "SkPath.h"
#include "SkPicture.h"
+#include "SkQuadTreePicture.h"
#include "SkRandom.h"
#include "SkRegion.h"
#include "SkShader.h"
@@ -61,8 +62,22 @@
SkString name("P:");
const char* basename = strrchr(fFilename.c_str(), SkPATH_SEPARATOR);
name.append(basename ? basename+1: fFilename.c_str());
- if (fBBox != kNo_BBoxType) {
- name.append(fBBox == kRTree_BBoxType ? " <bbox: R>" : " <bbox: T>");
+ switch (fBBox) {
+ case kNo_BBoxType:
+ // No name appended
+ break;
+ case kRTree_BBoxType:
+ name.append(" <bbox: R>");
+ break;
+ case kQuadTree_BBoxType:
+ name.append(" <bbox: Q>");
+ break;
+ case kTileGrid_BBoxType:
+ name.append(" <bbox: T>");
+ break;
+ default:
+ SkASSERT(false);
+ break;
}
SampleCode::TitleR(evt, name.c_str());
return true;
@@ -93,6 +108,7 @@
private:
enum BBoxType {
kNo_BBoxType,
+ kQuadTree_BBoxType,
kRTree_BBoxType,
kTileGrid_BBoxType,
@@ -152,6 +168,10 @@
case kRTree_BBoxType:
bboxPicture = SkNEW(SkPicture);
break;
+ case kQuadTree_BBoxType:
+ bboxPicture = SkNEW_ARGS(SkQuadTreePicture,
+ (SkIRect::MakeWH(pic->width(), pic->height())));
+ break;
case kTileGrid_BBoxType: {
SkASSERT(!fTileSize.isEmpty());
SkTileGridPicture::TileGridInfo gridInfo;