New approach for GPU font atlas
In the previous code, each GrTextStrike had exclusive access to one or more GrPlots in the texture atlas. This led to poor packing when only a few glyphs were used. This change allows GrTextStrikes to share GrPlots, thereby getting much better utilization of the entire texture.
BUG=skia:2224
R=robertphillips@google.com, bsalomon@google.com
Author: jvanverth@google.com
Review URL: https://codereview.chromium.org/177463003
git-svn-id: http://skia.googlecode.com/svn/trunk@13636 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/gpu/GrAtlas.cpp b/src/gpu/GrAtlas.cpp
index 646c213..c2fcf46 100644
--- a/src/gpu/GrAtlas.cpp
+++ b/src/gpu/GrAtlas.cpp
@@ -35,10 +35,6 @@
///////////////////////////////////////////////////////////////////////////////
-#ifdef SK_DEBUG
- static int gCounter;
-#endif
-
// for testing
#define FONT_CACHE_STATS 0
#if FONT_CACHE_STATS
@@ -46,7 +42,6 @@
#endif
GrPlot::GrPlot() : fDrawToken(NULL, 0)
- , fNext(NULL)
, fTexture(NULL)
, fAtlasMgr(NULL)
, fBytesPerPixel(1)
@@ -94,6 +89,11 @@
return true;
}
+void GrPlot::resetRects() {
+ SkASSERT(NULL != fRects);
+ fRects->reset();
+}
+
///////////////////////////////////////////////////////////////////////////////
GrAtlasMgr::GrAtlasMgr(GrGpu* gpu, GrPixelConfig config) {
@@ -104,19 +104,17 @@
// set up allocated plots
size_t bpp = GrBytesPerPixel(fPixelConfig);
- fPlots = SkNEW_ARRAY(GrPlot, (GR_PLOT_WIDTH*GR_PLOT_HEIGHT));
- fFreePlots = NULL;
- GrPlot* currPlot = fPlots;
+ fPlotArray = SkNEW_ARRAY(GrPlot, (GR_PLOT_WIDTH*GR_PLOT_HEIGHT));
+
+ GrPlot* currPlot = fPlotArray;
for (int y = GR_PLOT_HEIGHT-1; y >= 0; --y) {
for (int x = GR_PLOT_WIDTH-1; x >= 0; --x) {
currPlot->fAtlasMgr = this;
currPlot->fOffset.set(x, y);
currPlot->fBytesPerPixel = bpp;
- // add to free list
- currPlot->fNext = fFreePlots;
- fFreePlots = currPlot;
-
+ // build LRU list
+ fPlotList.addToHead(currPlot);
++currPlot;
}
}
@@ -124,7 +122,7 @@
GrAtlasMgr::~GrAtlasMgr() {
SkSafeUnref(fTexture);
- SkDELETE_ARRAY(fPlots);
+ SkDELETE_ARRAY(fPlotArray);
fGpu->unref();
#if FONT_CACHE_STATS
@@ -132,25 +130,29 @@
#endif
}
+void GrAtlasMgr::moveToHead(GrPlot* plot) {
+ if (fPlotList.head() == plot) {
+ return;
+ }
+
+ fPlotList.remove(plot);
+ fPlotList.addToHead(plot);
+};
+
GrPlot* GrAtlasMgr::addToAtlas(GrAtlas* atlas,
int width, int height, const void* image,
GrIPoint16* loc) {
- // iterate through entire plot list, see if we can find a hole
- GrPlot* plotIter = atlas->fPlots;
- while (plotIter) {
- if (plotIter->addSubImage(width, height, image, loc)) {
- return plotIter;
+ // iterate through entire plot list for this atlas, see if we can find a hole
+ // last one was most recently added and probably most empty
+ for (int i = atlas->fPlots.count()-1; i >= 0; --i) {
+ GrPlot* plot = atlas->fPlots[i];
+ if (plot->addSubImage(width, height, image, loc)) {
+ this->moveToHead(plot);
+ return plot;
}
- plotIter = plotIter->fNext;
}
- // If the above fails, then either we have no starting plot, or the current
- // plot list is full. Either way we need to allocate a new plot
- GrPlot* newPlot = this->allocPlot();
- if (NULL == newPlot) {
- return NULL;
- }
-
+ // before we get a new plot, make sure we have a backing texture
if (NULL == fTexture) {
// TODO: Update this to use the cache rather than directly creating a texture.
GrTextureDesc desc;
@@ -164,77 +166,53 @@
return NULL;
}
}
- // be sure to set texture for fast lookup
- newPlot->fTexture = fTexture;
- if (!newPlot->addSubImage(width, height, image, loc)) {
- this->freePlot(newPlot);
- return NULL;
+ // now look through all allocated plots for one we can share, in MRU order
+ GrPlotList::Iter plotIter;
+ plotIter.init(fPlotList, GrPlotList::Iter::kHead_IterStart);
+ GrPlot* plot;
+ while (NULL != (plot = plotIter.get())) {
+ // make sure texture is set for quick lookup
+ plot->fTexture = fTexture;
+ if (plot->addSubImage(width, height, image, loc)) {
+ this->moveToHead(plot);
+ // new plot for atlas, put at end of array
+ *(atlas->fPlots.append()) = plot;
+ return plot;
+ }
+ plotIter.next();
}
- // new plot, put at head
- newPlot->fNext = atlas->fPlots;
- atlas->fPlots = newPlot;
-
- return newPlot;
+ // If the above fails, then the current plot list has no room
+ return NULL;
}
-bool GrAtlasMgr::removeUnusedPlots(GrAtlas* atlas) {
-
- // GrPlot** is used so that the head element can be easily
- // modified when the first element is deleted
- GrPlot** plotRef = &atlas->fPlots;
- GrPlot* plot = atlas->fPlots;
- bool removed = false;
- while (NULL != plot) {
- if (plot->drawToken().isIssued()) {
- *plotRef = plot->fNext;
- this->freePlot(plot);
- plot = *plotRef;
- removed = true;
- } else {
- plotRef = &plot->fNext;
- plot = plot->fNext;
+bool GrAtlasMgr::removePlot(GrAtlas* atlas, const GrPlot* plot) {
+ // iterate through plot list for this atlas
+ int count = atlas->fPlots.count();
+ for (int i = 0; i < count; ++i) {
+ if (plot == atlas->fPlots[i]) {
+ atlas->fPlots.remove(i);
+ return true;
}
}
- return removed;
+ return false;
}
-void GrAtlasMgr::deletePlotList(GrPlot* plot) {
- while (NULL != plot) {
- GrPlot* next = plot->fNext;
- this->freePlot(plot);
- plot = next;
- }
-}
-
-GrPlot* GrAtlasMgr::allocPlot() {
- if (NULL == fFreePlots) {
- return NULL;
- } else {
- GrPlot* alloc = fFreePlots;
- fFreePlots = alloc->fNext;
-#ifdef SK_DEBUG
-// GrPrintf(" GrPlot %p [%d %d] %d\n", this, alloc->fOffset.fX, alloc->fOffset.fY, gCounter);
- gCounter += 1;
-#endif
- return alloc;
+// get a plot that's not being used by the current draw
+GrPlot* GrAtlasMgr::getUnusedPlot() {
+ GrPlotList::Iter plotIter;
+ plotIter.init(fPlotList, GrPlotList::Iter::kTail_IterStart);
+ GrPlot* plot;
+ while (NULL != (plot = plotIter.get())) {
+ if (plot->drawToken().isIssued()) {
+ return plot;
+ }
+ plotIter.prev();
}
-}
-
-void GrAtlasMgr::freePlot(GrPlot* plot) {
- SkASSERT(this == plot->fAtlasMgr);
-
- plot->fRects->reset();
- plot->fNext = fFreePlots;
- fFreePlots = plot;
-
-#ifdef SK_DEBUG
- --gCounter;
-// GrPrintf("~GrPlot %p [%d %d] %d\n", this, plot->fOffset.fX, plot->fOffset.fY, gCounter);
-#endif
+ return NULL;
}
SkISize GrAtlas::getSize() const {