Home | History | Annotate | Download | only in gpu 
      1 
      2 /*
      3  * Copyright 2010 Google Inc.
      4  *
      5  * Use of this source code is governed by a BSD-style license that can be
      6  * found in the LICENSE file.
      7  */
      8 
      9 
     10 
     11 #include "GrRectanizer.h"
     12 #include "GrTBSearch.h"
     13 
     14 #define MIN_HEIGHT_POW2     2
     15 
     16 class GrRectanizerPow2 : public GrRectanizer {
     17 public:
     18     GrRectanizerPow2(int w, int h) : GrRectanizer(w, h) {
     19         fNextStripY = 0;
     20         fAreaSoFar = 0;
     21         sk_bzero(fRows, sizeof(fRows));
     22     }
     23 
     24     virtual ~GrRectanizerPow2() {
     25     }
     26 
     27     virtual void reset() {
     28         fNextStripY = 0;
     29         fAreaSoFar = 0;
     30         sk_bzero(fRows, sizeof(fRows));
     31     }
     32 
     33     virtual bool addRect(int w, int h, GrIPoint16* loc);
     34 
     35     virtual float percentFull() const {
     36         return fAreaSoFar / ((float)this->width() * this->height());
     37     }
     38 
     39     virtual int stripToPurge(int height) const { return -1; }
     40     virtual void purgeStripAtY(int yCoord) { }
     41 
     42     ///////////////////////////////////////////////////////////////////////////
     43 
     44     struct Row {
     45         GrIPoint16  fLoc;
     46         int         fRowHeight;
     47 
     48         bool canAddWidth(int width, int containerWidth) const {
     49             return fLoc.fX + width <= containerWidth;
     50         }
     51     };
     52 
     53     Row fRows[16];
     54 
     55     static int HeightToRowIndex(int height) {
     56         SkASSERT(height >= MIN_HEIGHT_POW2);
     57         return 32 - SkCLZ(height - 1);
     58     }
     59 
     60     int fNextStripY;
     61     int32_t fAreaSoFar;
     62 
     63     bool canAddStrip(int height) const {
     64         return fNextStripY + height <= this->height();
     65     }
     66 
     67     void initRow(Row* row, int rowHeight) {
     68         row->fLoc.set(0, fNextStripY);
     69         row->fRowHeight = rowHeight;
     70         fNextStripY += rowHeight;
     71     }
     72 };
     73 
     74 bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) {
     75     if ((unsigned)width > (unsigned)this->width() ||
     76         (unsigned)height > (unsigned)this->height()) {
     77         return false;
     78     }
     79 
     80     int32_t area = width * height;
     81 
     82     /*
     83         We use bsearch, but there may be more than one row with the same height,
     84         so we actually search for height-1, which can only be a pow2 itself if
     85         height == 2. Thus we set a minimum height.
     86      */
     87     height = GrNextPow2(height);
     88     if (height < MIN_HEIGHT_POW2) {
     89         height = MIN_HEIGHT_POW2;
     90     }
     91 
     92     Row* row = &fRows[HeightToRowIndex(height)];
     93     SkASSERT(row->fRowHeight == 0 || row->fRowHeight == height);
     94 
     95     if (0 == row->fRowHeight) {
     96         if (!this->canAddStrip(height)) {
     97             return false;
     98         }
     99         this->initRow(row, height);
    100     } else {
    101         if (!row->canAddWidth(width, this->width())) {
    102             if (!this->canAddStrip(height)) {
    103                 return false;
    104             }
    105             // that row is now "full", so retarget our Row record for
    106             // another one
    107             this->initRow(row, height);
    108         }
    109     }
    110 
    111     SkASSERT(row->fRowHeight == height);
    112     SkASSERT(row->canAddWidth(width, this->width()));
    113     *loc = row->fLoc;
    114     row->fLoc.fX += width;
    115 
    116     SkASSERT(row->fLoc.fX <= this->width());
    117     SkASSERT(row->fLoc.fY <= this->height());
    118     SkASSERT(fNextStripY <= this->height());
    119     fAreaSoFar += area;
    120     return true;
    121 }
    122 
    123 ///////////////////////////////////////////////////////////////////////////////
    124 
    125 // factory is now in GrRectanizer_skyline.cpp
    126 //GrRectanizer* GrRectanizer::Factory(int width, int height) {
    127 //    return SkNEW_ARGS(GrRectanizerPow2, (width, height));
    128 //}
    129