From c22d1398089fdb95480fb3459b23e4931e4f5280 Mon Sep 17 00:00:00 2001 From: "commit-bot@chromium.org" Date: Mon, 3 Feb 2014 18:08:33 +0000 Subject: 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 --- src/core/SkQuadTreePicture.h | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 src/core/SkQuadTreePicture.h (limited to 'src/core/SkQuadTreePicture.h') 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 -- cgit v1.2.3