Support for variable glyph width in QSGDefaultDistanceFieldGlyphCache.

The glyphs are not stored in a fixed 64x64px tile anymore.
Glyphs are stored in area equal to <glyph_width> + 10 (margin) x 64px.
Allocation is now done with QSGAreaAllocator.
When glyph recycling is needed, unused glyphs are freed until the new
glyph can fit in the cache.

Change-Id: I179a8f17bfe35468bdb63bca5113ea4d0f06c414
Reviewed-by: Yoann Lopes <yoann.lopes@nokia.com>

4 files changed, 69 insertions, 71 deletions

diff --git a/src/quick/scenegraph/qsgadaptationlayer.cpp b/src/quick/scenegraph/qsgadaptationlayer.cpp
index 5c7aae0b59..083a9fb602 100644
--- a/src/quick/scenegraph/qsgadaptationlayer.cpp
+++ b/src/quick/scenegraph/qsgadaptationlayer.cpp
@@ -117,21 +117,22 @@ void QSGDistanceFieldGlyphCache::populate(const QVector<glyph_t> &glyphs)
         ++gd.ref;
         referencedGlyphs.insert(glyphIndex);
 
-        if (gd.texCoord.isValid() || newGlyphs.contains(glyphIndex))
+        if (gd.texCoord.isValid() || m_populatingGlyphs.contains(glyphIndex))
             continue;
 
-        gd.texCoord.width = 0;
-        gd.texCoord.height = 0;
+        m_populatingGlyphs.insert(glyphIndex);
 
-        if (!gd.boundingRect.isEmpty())
+        if (gd.boundingRect.isEmpty()) {
+            gd.texCoord.width = 0;
+            gd.texCoord.height = 0;
+        } else {
             newGlyphs.insert(glyphIndex);
+        }
     }
 
-    if (newGlyphs.isEmpty())
-        return;
-
     referenceGlyphs(referencedGlyphs);
-    requestGlyphs(newGlyphs);
+    if (!newGlyphs.isEmpty())
+        requestGlyphs(newGlyphs);
 }
 
 void QSGDistanceFieldGlyphCache::release(const QVector<glyph_t> &glyphs)
@@ -149,6 +150,8 @@ void QSGDistanceFieldGlyphCache::release(const QVector<glyph_t> &glyphs)
 
 void QSGDistanceFieldGlyphCache::update()
 {
+    m_populatingGlyphs.clear();
+
     if (m_pendingGlyphs.isEmpty())
         return;
 
diff --git a/src/quick/scenegraph/qsgadaptationlayer_p.h b/src/quick/scenegraph/qsgadaptationlayer_p.h
index 3c62ce03dd..c1b2afc8fa 100644
--- a/src/quick/scenegraph/qsgadaptationlayer_p.h
+++ b/src/quick/scenegraph/qsgadaptationlayer_p.h
@@ -189,7 +189,7 @@ public:
     }
     int distanceFieldRadius() const
     {
-        return QT_DISTANCEFIELD_DEFAULT_RADIUS / QT_DISTANCEFIELD_SCALE(m_doubleGlyphResolution);
+        return QT_DISTANCEFIELD_RADIUS(m_doubleGlyphResolution) / QT_DISTANCEFIELD_SCALE(m_doubleGlyphResolution);
     }
     int glyphCount() const { return m_glyphCount; }
     bool doubleGlyphResolution() const { return m_doubleGlyphResolution; }
@@ -216,6 +216,15 @@ protected:
         QPointF position;
     };
 
+    struct GlyphData {
+        Texture *texture;
+        TexCoord texCoord;
+        QRectF boundingRect;
+        quint32 ref;
+
+        GlyphData() : texture(0), ref(0) { }
+    };
+
     virtual void requestGlyphs(const QSet<glyph_t> &glyphs) = 0;
     virtual void storeGlyphs(const QHash<glyph_t, QImage> &glyphs) = 0;
     virtual void referenceGlyphs(const QSet<glyph_t> &glyphs) = 0;
@@ -231,20 +240,11 @@ protected:
     inline bool containsGlyph(glyph_t glyph);
     GLuint textureIdForGlyph(glyph_t glyph) const;
 
+    GlyphData &glyphData(glyph_t glyph);
+
     QOpenGLContext *ctx;
 
 private:
-    struct GlyphData {
-        Texture *texture;
-        TexCoord texCoord;
-        QRectF boundingRect;
-        quint32 ref;
-
-        GlyphData() : texture(0), ref(0) { }
-    };
-
-    GlyphData &glyphData(glyph_t glyph);
-
     QSGDistanceFieldGlyphCacheManager *m_manager;
 
     QRawFont m_referenceFont;
@@ -255,6 +255,7 @@ private:
     QList<Texture> m_textures;
     QHash<glyph_t, GlyphData> m_glyphsData;
     QDataBuffer<glyph_t> m_pendingGlyphs;
+    QSet<glyph_t> m_populatingGlyphs;
     QLinkedList<QSGDistanceFieldGlyphConsumer*> m_registeredNodes;
 
     static Texture s_emptyTexture;
diff --git a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp
index aa2c78f84a..917fb87726 100644
--- a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp
+++ b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache.cpp
@@ -44,6 +44,7 @@
 #include <QtGui/private/qdistancefield_p.h>
 #include <QtQuick/private/qsgdistancefieldutil_p.h>
 #include <qopenglfunctions.h>
+#include <qmath.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -55,8 +56,6 @@ QSGDefaultDistanceFieldGlyphCache::QSGDefaultDistanceFieldGlyphCache(QSGDistance
     , m_fbo(0)
     , m_blitProgram(0)
 {
-    m_currentTexture = createTextureInfo();
-
     m_blitVertexCoordinateArray[0] = -1.0f;
     m_blitVertexCoordinateArray[1] = -1.0f;
     m_blitVertexCoordinateArray[2] =  1.0f;
@@ -74,6 +73,8 @@ QSGDefaultDistanceFieldGlyphCache::QSGDefaultDistanceFieldGlyphCache(QSGDistance
     m_blitTextureCoordinateArray[5] = 1.0f;
     m_blitTextureCoordinateArray[6] = 0.0f;
     m_blitTextureCoordinateArray[7] = 1.0f;
+
+    m_areaAllocator = new QSGAreaAllocator(QSize(maxTextureSize(), m_maxTextureCount * maxTextureSize()));
 }
 
 QSGDefaultDistanceFieldGlyphCache::~QSGDefaultDistanceFieldGlyphCache()
@@ -82,6 +83,7 @@ QSGDefaultDistanceFieldGlyphCache::~QSGDefaultDistanceFieldGlyphCache()
         glDeleteTextures(1, &m_textures[i].texture);
     ctx->functions()->glDeleteFramebuffers(1, &m_fbo);
     delete m_blitProgram;
+    delete m_areaAllocator;
 }
 
 void QSGDefaultDistanceFieldGlyphCache::requestGlyphs(const QSet<glyph_t> &glyphs)
@@ -92,44 +94,42 @@ void QSGDefaultDistanceFieldGlyphCache::requestGlyphs(const QSet<glyph_t> &glyph
     for (QSet<glyph_t>::const_iterator it = glyphs.constBegin(); it != glyphs.constEnd() ; ++it) {
         glyph_t glyphIndex = *it;
 
-        if (cacheIsFull() && m_unusedGlyphs.isEmpty())
-            continue;
-
-        if (textureIsFull(m_currentTexture) && m_textures.count() < m_maxTextureCount)
-            m_currentTexture = createTextureInfo();
-
-        m_unusedGlyphs.remove(glyphIndex);
-
-        TextureInfo *tex = m_currentTexture;
+        int glyphWidth = qCeil(glyphData(glyphIndex).boundingRect.width()) + distanceFieldRadius() * 2;
+        QSize glyphSize(glyphWidth, QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution()));
+        QRect alloc = m_areaAllocator->allocate(glyphSize);
 
-        GlyphPosition p;
-        p.glyph = glyphIndex;
-        p.position = QPointF(tex->currX, tex->currY);
-
-        if (!cacheIsFull()) {
-            tex->currX += QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution());
-            if (tex->currX >= maxTextureSize()) {
-                tex->currX = 0;
-                tex->currY += QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution());
-            }
-        } else {
-            // Recycle glyphs
-            if (!m_unusedGlyphs.isEmpty()) {
+        if (alloc.isNull()) {
+            // Unallocate unused glyphs until we can allocated the new glyph
+            while (alloc.isNull() && !m_unusedGlyphs.isEmpty()) {
                 glyph_t unusedGlyph = *m_unusedGlyphs.constBegin();
+
                 TexCoord unusedCoord = glyphTexCoord(unusedGlyph);
-                tex = m_glyphsTexture.value(unusedGlyph);
-                p.position = QPointF(unusedCoord.x, unusedCoord.y);
+                int unusedGlyphWidth = qCeil(glyphData(unusedGlyph).boundingRect.width()) + distanceFieldRadius() * 2;
+                m_areaAllocator->deallocate(QRect(unusedCoord.x, unusedCoord.y, unusedGlyphWidth, QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution())));
+
                 m_unusedGlyphs.remove(unusedGlyph);
                 m_glyphsTexture.remove(unusedGlyph);
                 removeGlyph(unusedGlyph);
+
+                alloc = m_areaAllocator->allocate(glyphSize);
             }
-        }
 
-        if (p.position.y() < maxTextureSize()) {
-            glyphPositions.append(p);
-            glyphsToRender.append(glyphIndex);
-            m_glyphsTexture.insert(glyphIndex, tex);
+            // Not enough space left for this glyph... skip to the next one
+            if (alloc.isNull())
+                continue;
         }
+
+        TextureInfo *tex = textureInfo(alloc.y() / maxTextureSize());
+        alloc = QRect(alloc.x(), alloc.y() % maxTextureSize(), alloc.width(), alloc.height());
+        tex->allocatedArea |= alloc;
+
+        GlyphPosition p;
+        p.glyph = glyphIndex;
+        p.position = alloc.topLeft();
+
+        glyphPositions.append(p);
+        glyphsToRender.append(glyphIndex);
+        m_glyphsTexture.insert(glyphIndex, tex);
     }
 
     setGlyphsPosition(glyphPositions);
@@ -138,9 +138,6 @@ void QSGDefaultDistanceFieldGlyphCache::requestGlyphs(const QSet<glyph_t> &glyph
 
 void QSGDefaultDistanceFieldGlyphCache::storeGlyphs(const QHash<glyph_t, QImage> &glyphs)
 {
-    int requiredWidth = maxTextureSize();
-    int rows = 128 / (requiredWidth / QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution())); // Enough rows to fill the latin1 set by default..
-
     QHash<TextureInfo *, QVector<glyph_t> > glyphTextures;
 
     QHash<glyph_t, QImage>::const_iterator it;
@@ -149,16 +146,15 @@ void QSGDefaultDistanceFieldGlyphCache::storeGlyphs(const QHash<glyph_t, QImage>
         TexCoord c = glyphTexCoord(glyphIndex);
         TextureInfo *texInfo = m_glyphsTexture.value(glyphIndex);
 
-        int requiredHeight = qMin(maxTextureSize(),
-                                  qMax(texInfo->currY + QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution()),
-                                       QT_DISTANCEFIELD_TILESIZE(doubleGlyphResolution()) * rows));
-
-        resizeTexture(texInfo, requiredWidth, requiredHeight);
+        resizeTexture(texInfo, texInfo->allocatedArea.width(), texInfo->allocatedArea.height());
         glBindTexture(GL_TEXTURE_2D, texInfo->texture);
 
         glyphTextures[texInfo].append(glyphIndex);
 
         QImage glyph = it.value();
+        int expectedWidth = qCeil(c.width + c.xMargin * 2);
+        if (glyph.width() != expectedWidth)
+            glyph = glyph.copy(0, 0, expectedWidth, glyph.height());
 
         if (useWorkaroundBrokenFBOReadback()) {
             uchar *inBits = glyph.scanLine(0);
diff --git a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache_p.h b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache_p.h
index 5c38c1b656..c109280d0d 100644
--- a/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache_p.h
+++ b/src/quick/scenegraph/qsgdefaultdistancefieldglyphcache_p.h
@@ -46,6 +46,7 @@
 #include <QtGui/qopenglfunctions.h>
 #include <qopenglshaderprogram.h>
 #include <QtGui/private/qopenglengineshadersource_p.h>
+#include <private/qsgareaallocator_p.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -60,10 +61,6 @@ public:
     void referenceGlyphs(const QSet<glyph_t> &glyphs);
     void releaseGlyphs(const QSet<glyph_t> &glyphs);
 
-    bool cacheIsFull() const {
-        return m_textures.count() == m_maxTextureCount
-                && textureIsFull(m_currentTexture);
-    }
     bool useWorkaroundBrokenFBOReadback() const;
     int maxTextureSize() const;
 
@@ -74,22 +71,22 @@ private:
     struct TextureInfo {
         GLuint texture;
         QSize size;
-        int currX;
-        int currY;
+        QRect allocatedArea;
         QImage image;
 
-        TextureInfo() : texture(0), currX(0), currY(0)
+        TextureInfo() : texture(0)
         { }
     };
 
     void createTexture(TextureInfo * texInfo, int width, int height);
     void resizeTexture(TextureInfo * texInfo, int width, int height);
-    bool textureIsFull (const TextureInfo *tex) const { return tex->currY >= maxTextureSize(); }
 
-    TextureInfo *createTextureInfo()
+    TextureInfo *textureInfo(int index)
     {
-        m_textures.append(TextureInfo());
-        return &m_textures.last();
+        for (int i = m_textures.count(); i <= index; ++i)
+            m_textures.append(TextureInfo());
+
+        return &m_textures[index];
     }
 
     void createBlitProgram()
@@ -123,12 +120,13 @@ private:
     mutable int m_maxTextureSize;
     int m_maxTextureCount;
 
-    TextureInfo *m_currentTexture;
     QList<TextureInfo> m_textures;
     QHash<glyph_t, TextureInfo *> m_glyphsTexture;
     GLuint m_fbo;
     QSet<glyph_t> m_unusedGlyphs;
 
+    QSGAreaAllocator *m_areaAllocator;
+
     QOpenGLShaderProgram *m_blitProgram;
     GLfloat m_blitVertexCoordinateArray[8];
     GLfloat m_blitTextureCoordinateArray[8];