• file
• revisions
• annotate
• diff
• comparison
• raw

gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp@6474c204b198 (annotated)

gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Wed, 31 Dec 2014 06:09:35 +0100

changeset 0

6474c204b198

permissions

-rwxr-xr-x

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

michael@0	1
michael@0	2	/*
michael@0	3	* Copyright 2013 Google Inc.
michael@0	4	*
michael@0	5	* Use of this source code is governed by a BSD-style license that can be
michael@0	6	* found in the LICENSE file.
michael@0	7	*/
michael@0	8
michael@0	9	#include "GrRectanizer.h"
michael@0	10	#include "SkTDArray.h"
michael@0	11
michael@0	12	// Pack rectangles and track the current silhouette
michael@0	13	// Based in part on Jukka Jylänki's work at http://clb.demon.fi
michael@0	14
michael@0	15	class GrRectanizerSkyline : public GrRectanizer {
michael@0	16	public:
michael@0	17	GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) {
michael@0	18	reset();
michael@0	19	}
michael@0	20
michael@0	21	virtual ~GrRectanizerSkyline() {
michael@0	22	}
michael@0	23
michael@0	24	virtual void reset() {
michael@0	25	fAreaSoFar = 0;
michael@0	26	fSkyline.reset();
michael@0	27	SkylineSegment* seg = fSkyline.append(1);
michael@0	28	seg->fX = 0;
michael@0	29	seg->fY = 0;
michael@0	30	seg->fWidth = width();
michael@0	31	}
michael@0	32
michael@0	33	virtual bool addRect(int w, int h, GrIPoint16* loc);
michael@0	34
michael@0	35	virtual float percentFull() const {
michael@0	36	return fAreaSoFar / ((float)this->width() * this->height());
michael@0	37	}
michael@0	38
michael@0	39	virtual int stripToPurge(int height) const { return -1; }
michael@0	40	virtual void purgeStripAtY(int yCoord) { }
michael@0	41
michael@0	42	///////////////////////////////////////////////////////////////////////////
michael@0	43
michael@0	44	struct SkylineSegment {
michael@0	45	int fX;
michael@0	46	int fY;
michael@0	47	int fWidth;
michael@0	48	};
michael@0	49
michael@0	50	SkTDArray<SkylineSegment> fSkyline;
michael@0	51
michael@0	52	int32_t fAreaSoFar;
michael@0	53
michael@0	54	bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
michael@0	55	void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
michael@0	56	};
michael@0	57
michael@0	58	bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
michael@0	59	if ((unsigned)width > (unsigned)this->width() ||
michael@0	60	(unsigned)height > (unsigned)this->height()) {
michael@0	61	return false;
michael@0	62	}
michael@0	63
michael@0	64	// find position for new rectangle
michael@0	65	int bestWidth = this->width() + 1;
michael@0	66	int bestX;
michael@0	67	int bestY = this->height() + 1;
michael@0	68	int bestIndex = -1;
michael@0	69	for (int i = 0; i < fSkyline.count(); ++i) {
michael@0	70	int y;
michael@0	71	if (this->rectangleFits(i, width, height, &y)) {
michael@0	72	// minimize y position first, then width of skyline
michael@0	73	if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
michael@0	74	bestIndex = i;
michael@0	75	bestWidth = fSkyline[i].fWidth;
michael@0	76	bestX = fSkyline[i].fX;
michael@0	77	bestY = y;
michael@0	78	}
michael@0	79	}
michael@0	80	}
michael@0	81
michael@0	82	// add rectangle to skyline
michael@0	83	if (-1 != bestIndex) {
michael@0	84	this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
michael@0	85	loc->fX = bestX;
michael@0	86	loc->fY = bestY;
michael@0	87
michael@0	88	fAreaSoFar += width*height;
michael@0	89	return true;
michael@0	90	}
michael@0	91
michael@0	92	loc->fX = 0;
michael@0	93	loc->fY = 0;
michael@0	94	return false;
michael@0	95	}
michael@0	96
michael@0	97	bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
michael@0	98	int x = fSkyline[skylineIndex].fX;
michael@0	99	if (x + width > this->width()) {
michael@0	100	return false;
michael@0	101	}
michael@0	102
michael@0	103	int widthLeft = width;
michael@0	104	int i = skylineIndex;
michael@0	105	int y = fSkyline[skylineIndex].fY;
michael@0	106	while (widthLeft > 0) {
michael@0	107	y = SkMax32(y, fSkyline[i].fY);
michael@0	108	if (y + height > this->height()) {
michael@0	109	return false;
michael@0	110	}
michael@0	111	widthLeft -= fSkyline[i].fWidth;
michael@0	112	++i;
michael@0	113	SkASSERT(i < fSkyline.count() || widthLeft <= 0);
michael@0	114	}
michael@0	115
michael@0	116	*ypos = y;
michael@0	117	return true;
michael@0	118	}
michael@0	119
michael@0	120	void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
michael@0	121	SkylineSegment newSegment;
michael@0	122	newSegment.fX = x;
michael@0	123	newSegment.fY = y + height;
michael@0	124	newSegment.fWidth = width;
michael@0	125	fSkyline.insert(skylineIndex, 1, &newSegment);
michael@0	126
michael@0	127	SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
michael@0	128	SkASSERT(newSegment.fY <= this->height());
michael@0	129
michael@0	130	// delete width of this skyline segment from following ones
michael@0	131	for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
michael@0	132	SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
michael@0	133
michael@0	134	if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
michael@0	135	int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
michael@0	136
michael@0	137	fSkyline[i].fX += shrink;
michael@0	138	fSkyline[i].fWidth -= shrink;
michael@0	139
michael@0	140	if (fSkyline[i].fWidth <= 0) {
michael@0	141	fSkyline.remove(i);
michael@0	142	--i;
michael@0	143	}
michael@0	144	else
michael@0	145	break;
michael@0	146	}
michael@0	147	else
michael@0	148	break;
michael@0	149	}
michael@0	150
michael@0	151	// merge fSkylines
michael@0	152	for (int i = 0; i < fSkyline.count()-1; ++i) {
michael@0	153	if (fSkyline[i].fY == fSkyline[i+1].fY) {
michael@0	154	fSkyline[i].fWidth += fSkyline[i+1].fWidth;
michael@0	155	fSkyline.remove(i+1);
michael@0	156	--i;
michael@0	157	}
michael@0	158	}
michael@0	159	}
michael@0	160
michael@0	161	///////////////////////////////////////////////////////////////////////////////
michael@0	162
michael@0	163	GrRectanizer* GrRectanizer::Factory(int width, int height) {
michael@0	164	return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
michael@0	165	}