submodule/skia/src/gpu/RectanizerSkyline.cpp

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