109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org/* 309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org * Copyright 2013 Google Inc. 409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org * 509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org * Use of this source code is governed by a BSD-style license that can be 609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org * found in the LICENSE file. 709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org */ 809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 9ad854bf9c0d2029cf0730e50ac7f7ddbe32d1c97commit-bot@chromium.org#include "GrRectanizer_skyline.h" 10d537341e16524d1e22ac5e6c8b9c8f274ba1833crobertphillips#include "SkPoint.h" 1109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 12d537341e16524d1e22ac5e6c8b9c8f274ba1833crobertphillipsbool GrRectanizerSkyline::addRect(int width, int height, SkIPoint16* loc) { 1309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if ((unsigned)width > (unsigned)this->width() || 1409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org (unsigned)height > (unsigned)this->height()) { 1509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return false; 1609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 1709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 1809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org // find position for new rectangle 1909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int bestWidth = this->width() + 1; 2009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int bestX; 2109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int bestY = this->height() + 1; 2209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int bestIndex = -1; 2309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org for (int i = 0; i < fSkyline.count(); ++i) { 2409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int y; 2509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (this->rectangleFits(i, width, height, &y)) { 2609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org // minimize y position first, then width of skyline 2709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) { 2809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org bestIndex = i; 2909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org bestWidth = fSkyline[i].fWidth; 3009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org bestX = fSkyline[i].fX; 3109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org bestY = y; 3209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 3309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 3409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 3509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 3609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org // add rectangle to skyline 3709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (-1 != bestIndex) { 3809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org this->addSkylineLevel(bestIndex, bestX, bestY, width, height); 3909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org loc->fX = bestX; 4009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org loc->fY = bestY; 4109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 4209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fAreaSoFar += width*height; 4309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return true; 4409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 4509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 4609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org loc->fX = 0; 4709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org loc->fY = 0; 4809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return false; 4909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org} 5009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 5109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.orgbool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const { 5209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int x = fSkyline[skylineIndex].fX; 5309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (x + width > this->width()) { 5409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return false; 5509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 5609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 5709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int widthLeft = width; 5809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int i = skylineIndex; 5909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int y = fSkyline[skylineIndex].fY; 6009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org while (widthLeft > 0) { 6153e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org y = SkMax32(y, fSkyline[i].fY); 6209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (y + height > this->height()) { 6309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return false; 6409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 6553e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org widthLeft -= fSkyline[i].fWidth; 6653e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org ++i; 6753e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org SkASSERT(i < fSkyline.count() || widthLeft <= 0); 6809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 6909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 7009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org *ypos = y; 7109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return true; 7209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org} 7309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 7409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.orgvoid GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) { 7509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org SkylineSegment newSegment; 7609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org newSegment.fX = x; 7709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org newSegment.fY = y + height; 7809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org newSegment.fWidth = width; 7909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline.insert(skylineIndex, 1, &newSegment); 8009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 8109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org SkASSERT(newSegment.fX + newSegment.fWidth <= this->width()); 8209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org SkASSERT(newSegment.fY <= this->height()); 8309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 844cbf8e3dce10ef0d06e5ef95ea88b084bbad2553robertphillips // delete width of the new skyline segment from following ones 8509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org for (int i = skylineIndex+1; i < fSkyline.count(); ++i) { 864cbf8e3dce10ef0d06e5ef95ea88b084bbad2553robertphillips // The new segment subsumes all or part of fSkyline[i] 8709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX); 8809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 8909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) { 9009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX; 9109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 9209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline[i].fX += shrink; 9309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline[i].fWidth -= shrink; 9409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 9509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (fSkyline[i].fWidth <= 0) { 964cbf8e3dce10ef0d06e5ef95ea88b084bbad2553robertphillips // fully consumed 9709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline.remove(i); 9809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org --i; 9953e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org } else { 1004cbf8e3dce10ef0d06e5ef95ea88b084bbad2553robertphillips // only partially consumed 10109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org break; 10253e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org } 10353e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org } else { 10409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org break; 10553e1e4d88a06db62898a3bf75751c042729d7160commit-bot@chromium.org } 10609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 10709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 10809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org // merge fSkylines 10909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org for (int i = 0; i < fSkyline.count()-1; ++i) { 11009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org if (fSkyline[i].fY == fSkyline[i+1].fY) { 11109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline[i].fWidth += fSkyline[i+1].fWidth; 11209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org fSkyline.remove(i+1); 11309846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org --i; 11409846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 11509846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org } 11609846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org} 11709846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 11809846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org/////////////////////////////////////////////////////////////////////////////// 11909846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org 12009846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.orgGrRectanizer* GrRectanizer::Factory(int width, int height) { 12109846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org return SkNEW_ARGS(GrRectanizerSkyline, (width, height)); 12209846a05be093b610c91f7ff70610811ff3ee0f6commit-bot@chromium.org} 123