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