1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,165 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2013 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +#include "GrRectanizer.h"
1.13 +#include "SkTDArray.h"
1.14 +
1.15 +// Pack rectangles and track the current silhouette
1.16 +// Based in part on Jukka Jylänki's work at http://clb.demon.fi
1.17 +
1.18 +class GrRectanizerSkyline : public GrRectanizer {
1.19 +public:
1.20 + GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) {
1.21 + reset();
1.22 + }
1.23 +
1.24 + virtual ~GrRectanizerSkyline() {
1.25 + }
1.26 +
1.27 + virtual void reset() {
1.28 + fAreaSoFar = 0;
1.29 + fSkyline.reset();
1.30 + SkylineSegment* seg = fSkyline.append(1);
1.31 + seg->fX = 0;
1.32 + seg->fY = 0;
1.33 + seg->fWidth = width();
1.34 + }
1.35 +
1.36 + virtual bool addRect(int w, int h, GrIPoint16* loc);
1.37 +
1.38 + virtual float percentFull() const {
1.39 + return fAreaSoFar / ((float)this->width() * this->height());
1.40 + }
1.41 +
1.42 + virtual int stripToPurge(int height) const { return -1; }
1.43 + virtual void purgeStripAtY(int yCoord) { }
1.44 +
1.45 + ///////////////////////////////////////////////////////////////////////////
1.46 +
1.47 + struct SkylineSegment {
1.48 + int fX;
1.49 + int fY;
1.50 + int fWidth;
1.51 + };
1.52 +
1.53 + SkTDArray<SkylineSegment> fSkyline;
1.54 +
1.55 + int32_t fAreaSoFar;
1.56 +
1.57 + bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
1.58 + void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
1.59 +};
1.60 +
1.61 +bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
1.62 + if ((unsigned)width > (unsigned)this->width() ||
1.63 + (unsigned)height > (unsigned)this->height()) {
1.64 + return false;
1.65 + }
1.66 +
1.67 + // find position for new rectangle
1.68 + int bestWidth = this->width() + 1;
1.69 + int bestX;
1.70 + int bestY = this->height() + 1;
1.71 + int bestIndex = -1;
1.72 + for (int i = 0; i < fSkyline.count(); ++i) {
1.73 + int y;
1.74 + if (this->rectangleFits(i, width, height, &y)) {
1.75 + // minimize y position first, then width of skyline
1.76 + if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
1.77 + bestIndex = i;
1.78 + bestWidth = fSkyline[i].fWidth;
1.79 + bestX = fSkyline[i].fX;
1.80 + bestY = y;
1.81 + }
1.82 + }
1.83 + }
1.84 +
1.85 + // add rectangle to skyline
1.86 + if (-1 != bestIndex) {
1.87 + this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
1.88 + loc->fX = bestX;
1.89 + loc->fY = bestY;
1.90 +
1.91 + fAreaSoFar += width*height;
1.92 + return true;
1.93 + }
1.94 +
1.95 + loc->fX = 0;
1.96 + loc->fY = 0;
1.97 + return false;
1.98 +}
1.99 +
1.100 +bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
1.101 + int x = fSkyline[skylineIndex].fX;
1.102 + if (x + width > this->width()) {
1.103 + return false;
1.104 + }
1.105 +
1.106 + int widthLeft = width;
1.107 + int i = skylineIndex;
1.108 + int y = fSkyline[skylineIndex].fY;
1.109 + while (widthLeft > 0) {
1.110 + y = SkMax32(y, fSkyline[i].fY);
1.111 + if (y + height > this->height()) {
1.112 + return false;
1.113 + }
1.114 + widthLeft -= fSkyline[i].fWidth;
1.115 + ++i;
1.116 + SkASSERT(i < fSkyline.count() || widthLeft <= 0);
1.117 + }
1.118 +
1.119 + *ypos = y;
1.120 + return true;
1.121 +}
1.122 +
1.123 +void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
1.124 + SkylineSegment newSegment;
1.125 + newSegment.fX = x;
1.126 + newSegment.fY = y + height;
1.127 + newSegment.fWidth = width;
1.128 + fSkyline.insert(skylineIndex, 1, &newSegment);
1.129 +
1.130 + SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
1.131 + SkASSERT(newSegment.fY <= this->height());
1.132 +
1.133 + // delete width of this skyline segment from following ones
1.134 + for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
1.135 + SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
1.136 +
1.137 + if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
1.138 + int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
1.139 +
1.140 + fSkyline[i].fX += shrink;
1.141 + fSkyline[i].fWidth -= shrink;
1.142 +
1.143 + if (fSkyline[i].fWidth <= 0) {
1.144 + fSkyline.remove(i);
1.145 + --i;
1.146 + }
1.147 + else
1.148 + break;
1.149 + }
1.150 + else
1.151 + break;
1.152 + }
1.153 +
1.154 + // merge fSkylines
1.155 + for (int i = 0; i < fSkyline.count()-1; ++i) {
1.156 + if (fSkyline[i].fY == fSkyline[i+1].fY) {
1.157 + fSkyline[i].fWidth += fSkyline[i+1].fWidth;
1.158 + fSkyline.remove(i+1);
1.159 + --i;
1.160 + }
1.161 + }
1.162 +}
1.163 +
1.164 +///////////////////////////////////////////////////////////////////////////////
1.165 +
1.166 +GrRectanizer* GrRectanizer::Factory(int width, int height) {
1.167 + return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
1.168 +}
