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