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 "SkPoint.h" 13 14 // This Rectanizer quantizes the incoming rects to powers of 2. Each power 15 // of two can have, at most, one active row/shelf. Once a row/shelf for 16 // a particular power of two gets full its fRows entry is recycled to point 17 // to a new row. 18 // The skyline algorithm almost always provides a better packing. 19 class GrRectanizerPow2 : public GrRectanizer { 20 public: GrRectanizerPow2(int w,int h)21 GrRectanizerPow2(int w, int h) : INHERITED(w, h) { 22 this->reset(); 23 } 24 ~GrRectanizerPow2()25 virtual ~GrRectanizerPow2() { } 26 reset()27 void reset() override { 28 fNextStripY = 0; 29 fAreaSoFar = 0; 30 sk_bzero(fRows, sizeof(fRows)); 31 } 32 33 bool addRect(int w, int h, SkIPoint16* loc) override; 34 percentFull()35 float percentFull() const override { 36 return fAreaSoFar / ((float)this->width() * this->height()); 37 } 38 39 private: 40 static const int kMIN_HEIGHT_POW2 = 2; 41 static const int kMaxExponent = 16; 42 43 struct Row { 44 SkIPoint16 fLoc; 45 // fRowHeight is actually known by this struct's position in fRows 46 // but it is used to signal if there exists an open row of this height 47 int fRowHeight; 48 canAddWidthRow49 bool canAddWidth(int width, int containerWidth) const { 50 return fLoc.fX + width <= containerWidth; 51 } 52 }; 53 54 Row fRows[kMaxExponent]; // 0-th entry will be unused 55 56 int fNextStripY; 57 int32_t fAreaSoFar; 58 HeightToRowIndex(int height)59 static int HeightToRowIndex(int height) { 60 SkASSERT(height >= kMIN_HEIGHT_POW2); 61 int index = 32 - SkCLZ(height - 1); 62 SkASSERT(index < kMaxExponent); 63 return index; 64 } 65 canAddStrip(int height)66 bool canAddStrip(int height) const { 67 return fNextStripY + height <= this->height(); 68 } 69 initRow(Row * row,int rowHeight)70 void initRow(Row* row, int rowHeight) { 71 row->fLoc.set(0, fNextStripY); 72 row->fRowHeight = rowHeight; 73 fNextStripY += rowHeight; 74 } 75 76 typedef GrRectanizer INHERITED; 77 }; 78 79 #endif 80