15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Copyright 2014 Google Inc. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Use of this source code is governed by a BSD-style license that can be 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * found in the LICENSE file. 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 72a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef GrRectanizer_skyline_DEFINED 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define GrRectanizer_skyline_DEFINED 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 11c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "GrRectanizer.h" 12c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#include "SkTDArray.h" 13c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 14868fa2fe829687343ffae624259930155e16dbd8Torne (Richard Coles)// Pack rectangles and track the current silhouette 157d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles)// Based, in part, on Jukka Jylanki's work at http://clb.demon.fi 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class GrRectanizerSkyline : public GrRectanizer { 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)public: 181320f92c476a1ad9d19dba2a48c72b75566198e9Primiano Tucci GrRectanizerSkyline(int w, int h) : INHERITED(w, h) { 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) this->reset(); 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual ~GrRectanizerSkyline() { } 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) virtual void reset() SK_OVERRIDE{ 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fAreaSoFar = 0; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fSkyline.reset(); 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkylineSegment* seg = fSkyline.append(1); 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seg->fX = 0; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seg->fY = 0; 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seg->fWidth = this->width(); 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 3390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) virtual bool addRect(int w, int h, SkIPoint16* loc) SK_OVERRIDE; 347d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) 3590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) virtual float percentFull() const SK_OVERRIDE { 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return fAreaSoFar / ((float)this->width() * this->height()); 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 3990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)private: 4090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) struct SkylineSegment { 4190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) int fX; 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int fY; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int fWidth; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SkTDArray<SkylineSegment> fSkyline; 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32_t fAreaSoFar; 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Can a width x height rectangle fit in the free space represented by 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the skyline segments >= 'skylineIndex'? If so, return true and fill in 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'y' with the y-location at which it fits (the x location is pulled from 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 'skylineIndex's segment. 5490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool rectangleFits(int skylineIndex, int width, int height, int* y) const; 5590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Update the skyline structure to include a width x height rect located 5690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // at x,y. 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void addSkylineLevel(int skylineIndex, int x, int y, int width, int height); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 597d4cd473f85ac64c3747c96c277f9e506a0d2246Torne (Richard Coles) typedef GrRectanizer INHERITED; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 62c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles)#endif 6390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)