Line data    Source code

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