blob: 3c3928ed855a921411055ce00669a5f05e2cd856 [file] [log] [blame]
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +00001/*
2* Copyright 2014 Google Inc.
3*
4* Use of this source code is governed by a BSD-style license that can be
5* found in the LICENSE file.
6*/
7
8#ifndef GrRectanizer_pow2_DEFINED
9#define GrRectanizer_pow2_DEFINED
10
11#include "GrRectanizer.h"
halcanary4dbbd042016-06-07 17:21:10 -070012#include "SkMathPriv.h"
Herb Derbyb549cc32017-03-27 13:35:15 -040013#include "SkMalloc.h"
Mike Reed1fda0242018-04-04 15:39:46 -040014#include "SkIPoint16.h"
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000015
robertphillips901e96d2014-06-02 07:15:18 -070016// This Rectanizer quantizes the incoming rects to powers of 2. Each power
17// of two can have, at most, one active row/shelf. Once a row/shelf for
18// a particular power of two gets full its fRows entry is recycled to point
19// to a new row.
20// The skyline algorithm almost always provides a better packing.
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000021class GrRectanizerPow2 : public GrRectanizer {
22public:
23 GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
24 this->reset();
25 }
26
Brian Salomond3b65972017-03-22 12:05:03 -040027 ~GrRectanizerPow2() override {}
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000028
mtklein36352bf2015-03-25 18:17:31 -070029 void reset() override {
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000030 fNextStripY = 0;
31 fAreaSoFar = 0;
32 sk_bzero(fRows, sizeof(fRows));
33 }
34
mtklein36352bf2015-03-25 18:17:31 -070035 bool addRect(int w, int h, SkIPoint16* loc) override;
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000036
mtklein36352bf2015-03-25 18:17:31 -070037 float percentFull() const override {
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000038 return fAreaSoFar / ((float)this->width() * this->height());
39 }
40
41private:
42 static const int kMIN_HEIGHT_POW2 = 2;
robertphillips901e96d2014-06-02 07:15:18 -070043 static const int kMaxExponent = 16;
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000044
45 struct Row {
robertphillipsd5373412014-06-02 10:20:14 -070046 SkIPoint16 fLoc;
robertphillips901e96d2014-06-02 07:15:18 -070047 // fRowHeight is actually known by this struct's position in fRows
48 // but it is used to signal if there exists an open row of this height
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000049 int fRowHeight;
50
51 bool canAddWidth(int width, int containerWidth) const {
52 return fLoc.fX + width <= containerWidth;
53 }
54 };
55
robertphillips901e96d2014-06-02 07:15:18 -070056 Row fRows[kMaxExponent]; // 0-th entry will be unused
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000057
58 int fNextStripY;
59 int32_t fAreaSoFar;
60
61 static int HeightToRowIndex(int height) {
62 SkASSERT(height >= kMIN_HEIGHT_POW2);
robertphillips901e96d2014-06-02 07:15:18 -070063 int index = 32 - SkCLZ(height - 1);
64 SkASSERT(index < kMaxExponent);
65 return index;
commit-bot@chromium.orgad854bf2014-05-29 18:46:38 +000066 }
67
68 bool canAddStrip(int height) const {
69 return fNextStripY + height <= this->height();
70 }
71
72 void initRow(Row* row, int rowHeight) {
73 row->fLoc.set(0, fNextStripY);
74 row->fRowHeight = rowHeight;
75 fNextStripY += rowHeight;
76 }
77
78 typedef GrRectanizer INHERITED;
79};
80
81#endif