1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
/*
* Copyright 2010 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "GrRectanizer.h"
#include "GrTBSearch.h"
#define MIN_HEIGHT_POW2 2
class GrRectanizerPow2 : public GrRectanizer {
public:
GrRectanizerPow2(int w, int h) : GrRectanizer(w, h) {
fNextStripY = 0;
fAreaSoFar = 0;
Gr_bzero(fRows, sizeof(fRows));
}
virtual ~GrRectanizerPow2() {
}
virtual bool addRect(int w, int h, GrIPoint16* loc);
virtual float percentFull() const {
return fAreaSoFar / ((float)this->width() * this->height());
}
virtual int stripToPurge(int height) const { return -1; }
virtual void purgeStripAtY(int yCoord) { }
///////////////////////////////////////////////////////////////////////////
struct Row {
GrIPoint16 fLoc;
int fRowHeight;
bool canAddWidth(int width, int containerWidth) const {
return fLoc.fX + width <= containerWidth;
}
};
Row fRows[16];
static int HeightToRowIndex(int height) {
GrAssert(height >= MIN_HEIGHT_POW2);
return 32 - SkCLZ(height - 1);
}
int fNextStripY;
int32_t fAreaSoFar;
bool canAddStrip(int height) const {
return fNextStripY + height <= this->height();
}
void initRow(Row* row, int rowHeight) {
row->fLoc.set(0, fNextStripY);
row->fRowHeight = rowHeight;
fNextStripY += rowHeight;
}
};
bool GrRectanizerPow2::addRect(int width, int height, GrIPoint16* loc) {
if ((unsigned)width > (unsigned)this->width() ||
(unsigned)height > (unsigned)this->height()) {
return false;
}
int32_t area = width * height;
/*
We use bsearch, but there may be more than one row with the same height,
so we actually search for height-1, which can only be a pow2 itself if
height == 2. Thus we set a minimum height.
*/
height = GrNextPow2(height);
if (height < MIN_HEIGHT_POW2) {
height = MIN_HEIGHT_POW2;
}
Row* row = &fRows[HeightToRowIndex(height)];
GrAssert(row->fRowHeight == 0 || row->fRowHeight == height);
if (0 == row->fRowHeight) {
if (!this->canAddStrip(height)) {
return false;
}
this->initRow(row, height);
} else {
if (!row->canAddWidth(width, this->width())) {
if (!this->canAddStrip(height)) {
return false;
}
// that row is now "full", so retarget our Row record for
// another one
this->initRow(row, height);
}
}
GrAssert(row->fRowHeight == height);
GrAssert(row->canAddWidth(width, this->width()));
*loc = row->fLoc;
row->fLoc.fX += width;
GrAssert(row->fLoc.fX <= this->width());
GrAssert(row->fLoc.fY <= this->height());
GrAssert(fNextStripY <= this->height());
fAreaSoFar += area;
return true;
}
///////////////////////////////////////////////////////////////////////////////
GrRectanizer* GrRectanizer::Factory(int width, int height) {
return SkNEW_ARGS(GrRectanizerPow2, (width, height));
}
|
