Home | History | Annotate | Download | only in gpu 
      1 
      2 /*
      3  * Copyright 2013 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 #include "GrRectanizer_skyline.h"
     10 #include "SkPoint.h"
     11 
     12 bool GrRectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) {
     13     if ((unsigned)width > (unsigned)this->width() ||
     14         (unsigned)height > (unsigned)this->height()) {
     15         return false;
     16     }
     17 
     18     // find position for new rectangle
     19     int bestWidth = this->width() + 1;
     20     int bestX;
     21     int bestY = this->height() + 1;
     22     int bestIndex = -1;
     23     for (int i = 0; i < fSkyline.count(); ++i) {
     24         int y;
     25         if (this->rectangleFits(i, width, height, &y)) {
     26             // minimize y position first, then width of skyline
     27             if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
     28                 bestIndex = i;
     29                 bestWidth = fSkyline[i].fWidth;
     30                 bestX = fSkyline[i].fX;
     31                 bestY = y;
     32             }
     33         }
     34     }
     35 
     36     // add rectangle to skyline
     37     if (-1 != bestIndex) {
     38         this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
     39         loc->fX = bestX;
     40         loc->fY = bestY;
     41 
     42         fAreaSoFar += width*height;
     43         return true;
     44     }
     45 
     46     loc->fX = 0;
     47     loc->fY = 0;
     48     return false;
     49 }
     50 
     51 bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
     52     int x = fSkyline[skylineIndex].fX;
     53     if (x + width > this->width()) {
     54         return false;
     55     }
     56 
     57     int widthLeft = width;
     58     int i = skylineIndex;
     59     int y = fSkyline[skylineIndex].fY;
     60     while (widthLeft > 0) {
     61         y = SkMax32(y, fSkyline[i].fY);
     62         if (y + height > this->height()) {
     63             return false;
     64         }
     65         widthLeft -= fSkyline[i].fWidth;
     66         ++i;
     67         SkASSERT(i < fSkyline.count() || widthLeft <= 0);
     68     }
     69 
     70     *ypos = y;
     71     return true;
     72 }
     73 
     74 void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
     75     SkylineSegment newSegment;
     76     newSegment.fX = x;
     77     newSegment.fY = y + height;
     78     newSegment.fWidth = width;
     79     fSkyline.insert(skylineIndex, 1, &newSegment);
     80 
     81     SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
     82     SkASSERT(newSegment.fY <= this->height());
     83 
     84     // delete width of the new skyline segment from following ones
     85     for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
     86         // The new segment subsumes all or part of fSkyline[i]
     87         SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
     88 
     89         if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
     90             int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
     91 
     92             fSkyline[i].fX += shrink;
     93             fSkyline[i].fWidth -= shrink;
     94 
     95             if (fSkyline[i].fWidth <= 0) {
     96                 // fully consumed
     97                 fSkyline.remove(i);
     98                 --i;
     99             } else {
    100                 // only partially consumed
    101                 break;
    102             }
    103         } else {
    104             break;
    105         }
    106     }
    107 
    108     // merge fSkylines
    109     for (int i = 0; i < fSkyline.count()-1; ++i) {
    110         if (fSkyline[i].fY == fSkyline[i+1].fY) {
    111             fSkyline[i].fWidth += fSkyline[i+1].fWidth;
    112             fSkyline.remove(i+1);
    113             --i;
    114         }
    115     }
    116 }
    117 
    118 ///////////////////////////////////////////////////////////////////////////////
    119 
    120 GrRectanizer* GrRectanizer::Factory(int width, int height) {
    121     return new GrRectanizerSkyline(width, height);
    122 }
    123