Reland GrRectanizerPow2
This brings back the pow2 rectanizer for use with various ongoing
atlas experiments. If we can further optimize the skyline rectanizer,
then pow2 will be good to have around as a baseline comparison. And
if skyline gets fast enough, then we can delete pow2 again.
Change-Id: I79088c53fba7ba0d120534af99bee7840c135e42
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/290810
Reviewed-by: Robert Phillips <robertphillips@google.com>
Commit-Queue: Chris Dalton <csmartdalton@google.com>
diff --git a/src/gpu/GrDynamicAtlas.cpp b/src/gpu/GrDynamicAtlas.cpp
index 00d0947..1b00dc4 100644
--- a/src/gpu/GrDynamicAtlas.cpp
+++ b/src/gpu/GrDynamicAtlas.cpp
@@ -7,6 +7,7 @@
#include "src/gpu/GrDynamicAtlas.h"
+#include "src/core/SkIPoint16.h"
#include "src/gpu/GrOnFlushResourceProvider.h"
#include "src/gpu/GrProxyProvider.h"
#include "src/gpu/GrRectanizerSkyline.h"
diff --git a/src/gpu/GrRectanizer.h b/src/gpu/GrRectanizer.h
new file mode 100644
index 0000000..0b1fff5
--- /dev/null
+++ b/src/gpu/GrRectanizer.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2010 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef GrRectanizer_DEFINED
+#define GrRectanizer_DEFINED
+
+#include "include/gpu/GrTypes.h"
+
+struct SkIPoint16;
+
+class GrRectanizer {
+public:
+ GrRectanizer(int width, int height) : fWidth(width), fHeight(height) {
+ SkASSERT(width >= 0);
+ SkASSERT(height >= 0);
+ }
+
+ virtual ~GrRectanizer() {}
+
+ virtual void reset() = 0;
+
+ int width() const { return fWidth; }
+ int height() const { return fHeight; }
+
+ // Attempt to add a rect. Return true on success; false on failure. If
+ // successful the position in the atlas is returned in 'loc'.
+ virtual bool addRect(int width, int height, SkIPoint16* loc) = 0;
+ virtual float percentFull() const = 0;
+
+ /**
+ * Our factory, which returns the subclass du jour
+ */
+ static GrRectanizer* Factory(int width, int height);
+
+private:
+ const int fWidth;
+ const int fHeight;
+};
+
+#endif
diff --git a/src/gpu/GrRectanizerPow2.cpp b/src/gpu/GrRectanizerPow2.cpp
new file mode 100644
index 0000000..9a35bf2
--- /dev/null
+++ b/src/gpu/GrRectanizerPow2.cpp
@@ -0,0 +1,59 @@
+/*
+ * Copyright 2010 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "src/gpu/GrRectanizerPow2.h"
+
+bool GrRectanizerPow2::addRect(int width, int height, SkIPoint16* loc) {
+ if ((unsigned)width > (unsigned)this->width() ||
+ (unsigned)height > (unsigned)this->height()) {
+ return false;
+ }
+
+ int32_t area = width * height; // computed here since height will be modified
+
+ height = GrNextPow2(height);
+ if (height < kMIN_HEIGHT_POW2) {
+ height = kMIN_HEIGHT_POW2;
+ }
+
+ Row* row = &fRows[HeightToRowIndex(height)];
+ SkASSERT(row->fRowHeight == 0 || row->fRowHeight == height);
+
+ if (0 == row->fRowHeight) {
+ if (!this->canAddStrip(height)) {
+ return false;
+ }
+ this->initRow(row, height);
+ } else {
+ if (!row->canAddWidth(width, this->width())) {
+ if (!this->canAddStrip(height)) {
+ return false;
+ }
+ // that row is now "full", so retarget our Row record for
+ // another one
+ this->initRow(row, height);
+ }
+ }
+
+ SkASSERT(row->fRowHeight == height);
+ SkASSERT(row->canAddWidth(width, this->width()));
+ *loc = row->fLoc;
+ row->fLoc.fX += width;
+
+ SkASSERT(row->fLoc.fX <= this->width());
+ SkASSERT(row->fLoc.fY <= this->height());
+ SkASSERT(fNextStripY <= this->height());
+ fAreaSoFar += area;
+ return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+// factory is now in GrRectanizer_skyline.cpp
+//GrRectanizer* GrRectanizer::Factory(int width, int height) {
+// return new GrRectanizerPow2 (width, height);
+//}
diff --git a/src/gpu/GrRectanizerPow2.h b/src/gpu/GrRectanizerPow2.h
new file mode 100644
index 0000000..c96c9725
--- /dev/null
+++ b/src/gpu/GrRectanizerPow2.h
@@ -0,0 +1,83 @@
+/*
+* 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 GrRectanizerPow2_DEFINED
+#define GrRectanizerPow2_DEFINED
+
+#include "include/private/SkMalloc.h"
+#include "src/core/SkIPoint16.h"
+#include "src/core/SkMathPriv.h"
+#include "src/gpu/GrRectanizer.h"
+
+// This Rectanizer quantizes the incoming rects to powers of 2. Each power
+// of two can have, at most, one active row/shelf. Once a row/shelf for
+// a particular power of two gets full its fRows entry is recycled to point
+// to a new row.
+// The skyline algorithm almost always provides a better packing.
+//
+// Mark this class final in an effort to avoid the vtable when this subclass is used explicitly.
+class GrRectanizerPow2 final : public GrRectanizer {
+public:
+ GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
+ this->reset();
+ }
+
+ ~GrRectanizerPow2() final {}
+
+ void reset() final {
+ fNextStripY = 0;
+ fAreaSoFar = 0;
+ sk_bzero(fRows, sizeof(fRows));
+ }
+
+ bool addRect(int w, int h, SkIPoint16* loc) final;
+
+ float percentFull() const final {
+ return fAreaSoFar / ((float)this->width() * this->height());
+ }
+
+private:
+ static const int kMIN_HEIGHT_POW2 = 2;
+ static const int kMaxExponent = 16;
+
+ struct Row {
+ SkIPoint16 fLoc;
+ // fRowHeight is actually known by this struct's position in fRows
+ // but it is used to signal if there exists an open row of this height
+ int fRowHeight;
+
+ bool canAddWidth(int width, int containerWidth) const {
+ return fLoc.fX + width <= containerWidth;
+ }
+ };
+
+ Row fRows[kMaxExponent]; // 0-th entry will be unused
+
+ int fNextStripY;
+ int32_t fAreaSoFar;
+
+ static int HeightToRowIndex(int height) {
+ SkASSERT(height >= kMIN_HEIGHT_POW2);
+ int index = 32 - SkCLZ(height - 1);
+ SkASSERT(index < kMaxExponent);
+ return index;
+ }
+
+ bool canAddStrip(int height) const {
+ return fNextStripY + height <= this->height();
+ }
+
+ void initRow(Row* row, int rowHeight) {
+ row->fLoc.set(0, fNextStripY);
+ row->fRowHeight = rowHeight;
+ fNextStripY += rowHeight;
+ }
+
+ typedef GrRectanizer INHERITED;
+};
+
+#endif
diff --git a/src/gpu/GrRectanizerSkyline.cpp b/src/gpu/GrRectanizerSkyline.cpp
index 42aff7a..f36b733 100644
--- a/src/gpu/GrRectanizerSkyline.cpp
+++ b/src/gpu/GrRectanizerSkyline.cpp
@@ -116,3 +116,8 @@
}
}
+///////////////////////////////////////////////////////////////////////////////
+
+GrRectanizer* GrRectanizer::Factory(int width, int height) {
+ return new GrRectanizerSkyline(width, height);
+}
diff --git a/src/gpu/GrRectanizerSkyline.h b/src/gpu/GrRectanizerSkyline.h
index 36af34d..40e5c1c 100644
--- a/src/gpu/GrRectanizerSkyline.h
+++ b/src/gpu/GrRectanizerSkyline.h
@@ -9,17 +9,21 @@
#define GrRectanizerSkyline_DEFINED
#include "include/private/SkTDArray.h"
-#include "src/core/SkIPoint16.h"
+#include "src/gpu/GrRectanizer.h"
// Pack rectangles and track the current silhouette
// Based, in part, on Jukka Jylanki's work at http://clb.demon.fi
-class GrRectanizerSkyline {
+//
+// Mark this class final in an effort to avoid the vtable when this subclass is used explicitly.
+class GrRectanizerSkyline final : public GrRectanizer {
public:
- GrRectanizerSkyline(int w, int h) : fWidth{w}, fHeight{h} {
+ GrRectanizerSkyline(int w, int h) : INHERITED(w, h) {
this->reset();
}
- void reset() {
+ ~GrRectanizerSkyline() final { }
+
+ void reset() final {
fAreaSoFar = 0;
fSkyline.reset();
SkylineSegment* seg = fSkyline.append(1);
@@ -28,10 +32,11 @@
seg->fWidth = this->width();
}
- bool addRect(int w, int h, SkIPoint16* loc);
+ bool addRect(int w, int h, SkIPoint16* loc) final;
- int width() const { return fWidth; }
- int height() const { return fHeight; }
+ float percentFull() const final {
+ return fAreaSoFar / ((float)this->width() * this->height());
+ }
private:
struct SkylineSegment {
@@ -40,6 +45,10 @@
int fWidth;
};
+ SkTDArray<SkylineSegment> fSkyline;
+
+ int32_t fAreaSoFar;
+
// Can a width x height rectangle fit in the free space represented by
// the skyline segments >= 'skylineIndex'? If so, return true and fill in
// 'y' with the y-location at which it fits (the x location is pulled from
@@ -49,10 +58,7 @@
// at x,y.
void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
- const int fWidth;
- const int fHeight;
- SkTDArray<SkylineSegment> fSkyline;
- int32_t fAreaSoFar;
+ typedef GrRectanizer INHERITED;
};
-#endif // GrRectanizerSkyline_DEFINED
+#endif