• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
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"
12 #include "SkMathPriv.h"
13 #include "SkMalloc.h"
14 #include "SkPoint.h"
15 
16 // 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.
21 class GrRectanizerPow2 : public GrRectanizer {
22 public:
GrRectanizerPow2(int w,int h)23     GrRectanizerPow2(int w, int h) : INHERITED(w, h) {
24         this->reset();
25     }
26 
~GrRectanizerPow2()27     ~GrRectanizerPow2() override {}
28 
reset()29     void reset() override {
30         fNextStripY = 0;
31         fAreaSoFar = 0;
32         sk_bzero(fRows, sizeof(fRows));
33     }
34 
35     bool addRect(int w, int h, SkIPoint16* loc) override;
36 
percentFull()37     float percentFull() const override {
38         return fAreaSoFar / ((float)this->width() * this->height());
39     }
40 
41 private:
42     static const int kMIN_HEIGHT_POW2 = 2;
43     static const int kMaxExponent = 16;
44 
45     struct Row {
46         SkIPoint16  fLoc;
47         // 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
49         int         fRowHeight;
50 
canAddWidthRow51         bool canAddWidth(int width, int containerWidth) const {
52             return fLoc.fX + width <= containerWidth;
53         }
54     };
55 
56     Row fRows[kMaxExponent];    // 0-th entry will be unused
57 
58     int fNextStripY;
59     int32_t fAreaSoFar;
60 
HeightToRowIndex(int height)61     static int HeightToRowIndex(int height) {
62         SkASSERT(height >= kMIN_HEIGHT_POW2);
63         int index = 32 - SkCLZ(height - 1);
64         SkASSERT(index < kMaxExponent);
65         return index;
66     }
67 
canAddStrip(int height)68     bool canAddStrip(int height) const {
69         return fNextStripY + height <= this->height();
70     }
71 
initRow(Row * row,int rowHeight)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
82