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