use surface atlas for Skia text drawing on Windows

Just like with the OpenGL case the idea is that rather than caching
many tiny surfaces for each glyph it should be more efficient to have
large surfaces with the glyphs packed inside.

Change-Id: I4bc6ece40d4bc85d373340bd03f959fde3a45abf
Reviewed-on: https://gerrit.libreoffice.org/c/core/+/86777
Tested-by: Jenkins
Reviewed-by: Luboš Luňák <l.lunak@collabora.com>

8 files changed, 312 insertions, 38 deletions

diff --git a/vcl/Library_vcl.mk b/vcl/Library_vcl.mk
index e2a3fc9fb889..3a7122f15b11 100644
--- a/vcl/Library_vcl.mk
+++ b/vcl/Library_vcl.mk
@@ -589,6 +589,7 @@ $(eval $(call gb_Library_add_exception_objects,vcl,\
     vcl/source/opengl/OpenGLHelper \
     vcl/skia/SkiaHelper \
     $(if $(filter SKIA,$(BUILD_TYPE)), \
+        vcl/skia/packedsurfaceatlas \
         vcl/skia/salbmp \
         vcl/skia/gdiimpl) \
  ))
diff --git a/vcl/inc/skia/packedsurfaceatlas.hxx b/vcl/inc/skia/packedsurfaceatlas.hxx
new file mode 100644
index 000000000000..ee0b924192af
--- /dev/null
+++ b/vcl/inc/skia/packedsurfaceatlas.hxx
@@ -0,0 +1,83 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ */
+
+#ifndef INCLUDED_VCL_INC_SKIA_PACKEDSURFACEATLAS_HXX
+#define INCLUDED_VCL_INC_SKIA_PACKEDSURFACEATLAS_HXX
+
+#include <memory>
+
+#include <SkSurface.h>
+
+#include <vcl/dllapi.h>
+#include <tools/gen.hxx>
+
+/**
+ * SkSurface that is actually packed in a larger SkSurface atlas.
+ *
+ * In Skia's case we draw into SkSurface (as that's what's GPU-backed),
+ * but then for using the result we need to get an associated SkImage.
+ * The use of SkSurface::makeImageSnapshot() complicates thingss in two ways:
+ * - it does data copy if we want a sub-rectangle, so we need to pass a reference
+ *   and the geometry wanted
+ * - it does a snapshot of the state, meaning any further drawing into the SkSurface
+ *   would detach by creating a copy, so we need to pass around the SkSurface
+ *   reference and then create only a temporary SkImage for the whole SkSurface
+ *   (which should be almost a no-op)
+ */
+class VCL_DLLPUBLIC SkiaPackedSurface
+{
+public:
+    sk_sp<SkSurface> mSurface;
+    tools::Rectangle mRect; // the area in the surface that is this "surface"
+    SkiaPackedSurface(const sk_sp<SkSurface>& surface, const tools::Rectangle& rect)
+        : mSurface(surface)
+        , mRect(rect)
+    {
+    }
+    SkiaPackedSurface() = default;
+};
+
+/**
+ * Pack Skia "surfaces" into one surface atlas.
+ *
+ * This is based on algorithm described in [1] and is an
+ * adaptation of "texture atlas generator" from [2].
+ *
+ * [1]: http://www.blackpawn.com/texts/lightmaps/
+ * [2]: https://github.com/lukaszdk/texture-atlas-generator
+ *
+ */
+class VCL_DLLPUBLIC SkiaPackedSurfaceAtlasManager final
+{
+    struct PackedSurface;
+    std::vector<std::unique_ptr<PackedSurface>> maPackedSurfaces;
+
+    int const mnSurfaceWidth;
+    int const mnSurfaceHeight;
+
+    void CreateNewSurface();
+
+    SkiaPackedSurfaceAtlasManager(const SkiaPackedSurfaceAtlasManager&) = delete;
+    SkiaPackedSurfaceAtlasManager& operator=(const SkiaPackedSurfaceAtlasManager&) = delete;
+
+public:
+    /**
+     * nSurfaceWidth and nSurfaceHeight are the dimensions of the common surface(s)
+     */
+    SkiaPackedSurfaceAtlasManager(int nSurfaceWidth, int nSurfaceHeight);
+    ~SkiaPackedSurfaceAtlasManager();
+
+    SkiaPackedSurface Reserve(int nWidth, int nHeight);
+    std::vector<sk_sp<SkSurface>> ReduceSurfaceNumber(int nMaxNumberOfSurfaces);
+};
+
+#endif // INCLUDED_VCL_INC_SKIA_PACKEDSURFACEATLAS_HXX
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/vcl/inc/skia/win/gdiimpl.hxx b/vcl/inc/skia/win/gdiimpl.hxx
index daf41e8e06d0..7f11e4da628c 100644
--- a/vcl/inc/skia/win/gdiimpl.hxx
+++ b/vcl/inc/skia/win/gdiimpl.hxx
@@ -14,6 +14,7 @@
 #include <vcl/dllapi.h>
 
 #include <skia/gdiimpl.hxx>
+#include <skia/packedsurfaceatlas.hxx>
 #include <win/salgdi.h>
 #include <win/wingdiimpl.hxx>
 #include <o3tl/lru_map.hxx>
@@ -35,6 +36,7 @@ public:
     sk_sp<SkImage> getAsMaskImage() const;
 
     struct Texture;
+    struct PackedTexture;
 };
 
 struct SkiaCompatibleDC::Texture : public CompatibleDC::Texture
@@ -45,6 +47,14 @@ struct SkiaCompatibleDC::Texture : public CompatibleDC::Texture
     virtual int GetHeight() const { return image->height(); }
 };
 
+struct SkiaCompatibleDC::PackedTexture : public CompatibleDC::Texture
+{
+    SkiaPackedSurface packedSurface;
+    virtual bool isValid() const { return packedSurface.mSurface.get(); }
+    virtual int GetWidth() const { return packedSurface.mRect.GetWidth(); }
+    virtual int GetHeight() const { return packedSurface.mRect.GetHeight(); }
+};
+
 class WinSkiaSalGraphicsImpl : public SkiaSalGraphicsImpl, public WinSalGraphicsImplBase
 {
 private:
diff --git a/vcl/inc/skia/win/winlayout.hxx b/vcl/inc/skia/win/winlayout.hxx
index 32b2aea266a5..649fe993b05a 100644
--- a/vcl/inc/skia/win/winlayout.hxx
+++ b/vcl/inc/skia/win/winlayout.hxx
@@ -24,22 +24,26 @@
 
 #include <vector>
 
+#include <skia/packedsurfaceatlas.hxx>
+
 struct SkiaGlobalWinGlyphCache : public GlobalWinGlyphCache
 {
+    SkiaGlobalWinGlyphCache()
+        : mPackedSurfaceAtlas(2048, 2048)
+    {
+    }
+    SkiaPackedSurfaceAtlasManager mPackedSurfaceAtlas;
     virtual bool AllocateTexture(WinGlyphDrawElement& rElement, CompatibleDC* dc) override;
-    virtual void NotifyElementUsed(WinGlyphDrawElement& rElement) override;
     virtual void Prune() override;
-    // The least recently used SkImage order, identified by SkImage::uniqueID().
-    std::vector<uint32_t> mLRUOrder;
 };
 
 class SkiaWinGlyphCache : public WinGlyphCache
 {
 public:
-    void RemoveTextures(const std::vector<uint32_t>& ids);
+    void RemoveSurfaces(const std::vector<sk_sp<SkSurface>>& surfaces);
 
 private:
-    // This class just "adds" RemoveTexture() to the base class, it's never instantiatied.
+    // This class just "adds" RemoveSurfaces() to the base class, it's never instantiated.
     SkiaWinGlyphCache() = delete;
 };
 
diff --git a/vcl/inc/win/winlayout.hxx b/vcl/inc/win/winlayout.hxx
index d8cdd310b50f..c8da95d3fb3c 100644
--- a/vcl/inc/win/winlayout.hxx
+++ b/vcl/inc/win/winlayout.hxx
@@ -66,7 +66,6 @@ struct GlobalWinGlyphCache
 
     virtual ~GlobalWinGlyphCache() {}
     virtual bool AllocateTexture(WinGlyphDrawElement& rElement, CompatibleDC* dc) = 0;
-    virtual void NotifyElementUsed(WinGlyphDrawElement& /*rElement*/) {}
     virtual void Prune() {}
 };
 
@@ -99,9 +98,7 @@ public:
     {
         assert(GlobalWinGlyphCache::get());
         assert(IsGlyphCached(nGlyphIndex));
-        WinGlyphDrawElement& element = maWinTextureCache[nGlyphIndex];
-        GlobalWinGlyphCache::get()->NotifyElementUsed(element);
-        return element;
+        return maWinTextureCache[nGlyphIndex];
     }
 
     bool IsGlyphCached(int nGlyphIndex) const
diff --git a/vcl/skia/packedsurfaceatlas.cxx b/vcl/skia/packedsurfaceatlas.cxx
new file mode 100644
index 000000000000..b3ce81154856
--- /dev/null
+++ b/vcl/skia/packedsurfaceatlas.cxx
@@ -0,0 +1,175 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ */
+
+#include <skia/packedsurfaceatlas.hxx>
+
+#include <memory>
+#include <assert.h>
+
+#include <sal/config.h>
+#include <sal/log.hxx>
+
+#include <skia/utils.hxx>
+
+namespace
+{
+struct Node
+{
+    tools::Rectangle const mRectangle;
+    std::unique_ptr<Node> mLeftNode;
+    std::unique_ptr<Node> mRightNode;
+    bool mOccupied;
+
+    explicit Node(int nWidth, int nHeight);
+    explicit Node(tools::Rectangle const& aRectangle);
+
+    bool isLeaf() const;
+    Node* insert(int nWidth, int nHeight, int nPadding);
+};
+}
+
+Node::Node(int nWidth, int nHeight)
+    : mRectangle(tools::Rectangle(Point(), Size(nWidth, nHeight)))
+    , mLeftNode()
+    , mRightNode()
+    , mOccupied(false)
+{
+}
+
+Node::Node(tools::Rectangle const& aRectangle)
+    : mRectangle(aRectangle)
+    , mLeftNode()
+    , mRightNode()
+    , mOccupied(false)
+{
+}
+
+bool Node::isLeaf() const { return mLeftNode == nullptr && mRightNode == nullptr; }
+
+Node* Node::insert(int nWidth, int nHeight, int nPadding)
+{
+    if (!isLeaf())
+    {
+        Node* pNewNode = mLeftNode->insert(nWidth, nHeight, nPadding);
+
+        if (pNewNode != nullptr)
+            return pNewNode;
+
+        return mRightNode->insert(nWidth, nHeight, nPadding);
+    }
+    else
+    {
+        if (mOccupied)
+        {
+            return nullptr;
+        }
+
+        if (nWidth > mRectangle.GetWidth() || nHeight > mRectangle.GetHeight())
+        { // does not fit
+            return nullptr;
+        }
+
+        if (nWidth == mRectangle.GetWidth() && nHeight == mRectangle.GetHeight())
+        { // perfect fit
+            mOccupied = true;
+            return this;
+        }
+
+        int dw = mRectangle.GetWidth() - nWidth;
+        int dh = mRectangle.GetHeight() - nHeight;
+
+        tools::Rectangle aLeftRect;
+        tools::Rectangle aRightRect;
+        if (dw > dh)
+        {
+            aLeftRect = tools::Rectangle(Point(mRectangle.Left(), mRectangle.Top()),
+                                         Size(nWidth, mRectangle.GetHeight()));
+            aRightRect = tools::Rectangle(
+                Point(nPadding + mRectangle.Left() + nWidth, mRectangle.Top()),
+                Size(mRectangle.GetWidth() - nWidth - nPadding, mRectangle.GetHeight()));
+        }
+        else
+        {
+            aLeftRect = tools::Rectangle(Point(mRectangle.Left(), mRectangle.Top()),
+                                         Size(mRectangle.GetWidth(), nHeight));
+            aRightRect = tools::Rectangle(
+                Point(mRectangle.Left(), nPadding + mRectangle.Top() + nHeight),
+                Size(mRectangle.GetWidth(), mRectangle.GetHeight() - nHeight - nPadding));
+        }
+
+        mLeftNode.reset(new Node(aLeftRect));
+        mRightNode.reset(new Node(aRightRect));
+
+        return mLeftNode->insert(nWidth, nHeight, nPadding);
+    }
+}
+
+struct SkiaPackedSurfaceAtlasManager::PackedSurface
+{
+    sk_sp<SkSurface> mpSurface;
+    std::unique_ptr<Node> mpRootNode;
+
+    PackedSurface(int nWidth, int nHeight)
+        : mpSurface(SkiaHelper::createSkSurface(nWidth, nHeight))
+        , mpRootNode(new Node(nWidth, nHeight))
+    {
+        assert(mpSurface);
+    }
+};
+
+SkiaPackedSurfaceAtlasManager::SkiaPackedSurfaceAtlasManager(int nSurfaceWidth, int nSurfaceHeight)
+    : mnSurfaceWidth(nSurfaceWidth)
+    , mnSurfaceHeight(nSurfaceHeight)
+{
+}
+
+SkiaPackedSurfaceAtlasManager::~SkiaPackedSurfaceAtlasManager() {}
+
+void SkiaPackedSurfaceAtlasManager::CreateNewSurface()
+{
+    std::unique_ptr<PackedSurface> pPackedSurface(
+        new PackedSurface(mnSurfaceWidth, mnSurfaceHeight));
+    maPackedSurfaces.push_back(std::move(pPackedSurface));
+    SAL_INFO("vcl.skia",
+             "SkiaPackedSurfaceAtlas adding surface, count: " << maPackedSurfaces.size());
+}
+
+SkiaPackedSurface SkiaPackedSurfaceAtlasManager::Reserve(int nWidth, int nHeight)
+{
+    for (std::unique_ptr<PackedSurface>& pPackedSurface : maPackedSurfaces)
+    {
+        Node* pNode = pPackedSurface->mpRootNode->insert(nWidth, nHeight, 1);
+        if (pNode != nullptr)
+            return SkiaPackedSurface(pPackedSurface->mpSurface, pNode->mRectangle);
+    }
+    CreateNewSurface();
+    std::unique_ptr<PackedSurface>& pPackedSurface = maPackedSurfaces.back();
+    Node* pNode = pPackedSurface->mpRootNode->insert(nWidth, nHeight, 1);
+    if (pNode != nullptr)
+        return SkiaPackedSurface(pPackedSurface->mpSurface, pNode->mRectangle);
+    return SkiaPackedSurface();
+}
+
+std::vector<sk_sp<SkSurface>>
+SkiaPackedSurfaceAtlasManager::ReduceSurfaceNumber(int nMaxNumberOfSurfaces)
+{
+    std::vector<sk_sp<SkSurface>> aSurfaces;
+    while (int(maPackedSurfaces.size()) > nMaxNumberOfSurfaces)
+    {
+        // Remove oldest created surface
+        aSurfaces.push_back(maPackedSurfaces[0]->mpSurface);
+        maPackedSurfaces.erase(maPackedSurfaces.begin());
+        SAL_INFO("vcl.skia",
+                 "PackedSurfaceAtlas removing surface, count: " << maPackedSurfaces.size());
+    }
+    return aSurfaces;
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/vcl/skia/win/gdiimpl.cxx b/vcl/skia/win/gdiimpl.cxx
index 437e7c7d1e3f..ebaa81aa986a 100644
--- a/vcl/skia/win/gdiimpl.cxx
+++ b/vcl/skia/win/gdiimpl.cxx
@@ -136,16 +136,24 @@ static SkColor toSkColor(Color color)
 void WinSkiaSalGraphicsImpl::DeferredTextDraw(const CompatibleDC::Texture* pTexture,
                                               Color aMaskColor, const SalTwoRect& rPosAry)
 {
-    assert(dynamic_cast<const SkiaCompatibleDC::Texture*>(pTexture));
+    assert(dynamic_cast<const SkiaCompatibleDC::PackedTexture*>(pTexture));
+    const SkiaCompatibleDC::PackedTexture* texture
+        = static_cast<const SkiaCompatibleDC::PackedTexture*>(pTexture);
     preDraw();
     SkPaint paint;
     // The glyph is painted as white, modulate it to be of the appropriate color.
     // SkiaCompatibleDC::wantsTextColorWhite() ensures the glyph is white.
     // TODO maybe other black/white in WinFontInstance::CacheGlyphToAtlas() should be swapped.
     paint.setColorFilter(SkColorFilters::Blend(toSkColor(aMaskColor), SkBlendMode::kModulate));
+    // We use SkiaPackedSurface, so use also the appropriate rectangle in the source SkSurface.
+    const tools::Rectangle& rect = texture->packedSurface.mRect;
+    // The source in SalTwoRect is actually just the size.
+    assert(rPosAry.mnSrcX == 0 && rPosAry.mnSrcY == 0);
+    assert(rPosAry.mnSrcWidth == rect.GetWidth());
+    assert(rPosAry.mnSrcHeight == rect.GetHeight());
     mSurface->getCanvas()->drawImageRect(
-        static_cast<const SkiaCompatibleDC::Texture*>(pTexture)->image,
-        SkRect::MakeXYWH(rPosAry.mnSrcX, rPosAry.mnSrcY, rPosAry.mnSrcWidth, rPosAry.mnSrcHeight),
+        texture->packedSurface.mSurface->makeImageSnapshot(),
+        SkRect::MakeXYWH(rect.getX(), rect.getY(), rect.GetWidth(), rect.GetHeight()),
         SkRect::MakeXYWH(rPosAry.mnDestX, rPosAry.mnDestY, rPosAry.mnDestWidth,
                          rPosAry.mnDestHeight),
         &paint);
diff --git a/vcl/skia/win/winlayout.cxx b/vcl/skia/win/winlayout.cxx
index e544943b0e3f..bf46f8727c87 100644
--- a/vcl/skia/win/winlayout.cxx
+++ b/vcl/skia/win/winlayout.cxx
@@ -16,47 +16,43 @@ bool SkiaGlobalWinGlyphCache::AllocateTexture(WinGlyphDrawElement& rElement, Com
     assert(rElement.maTexture.get() == nullptr);
     assert(dynamic_cast<SkiaCompatibleDC*>(dc));
     SkiaCompatibleDC* sdc = static_cast<SkiaCompatibleDC*>(dc);
-    SkiaCompatibleDC::Texture* texture = new SkiaCompatibleDC::Texture;
+    SkiaCompatibleDC::PackedTexture* texture = new SkiaCompatibleDC::PackedTexture;
     rElement.maTexture.reset(texture);
-    // TODO is it possible to have an atlas?
-    texture->image = sdc->getAsImage();
-    mLRUOrder.push_back(texture->image->uniqueID());
+    texture->packedSurface
+        = mPackedSurfaceAtlas.Reserve(sdc->getBitmapWidth(), sdc->getBitmapHeight());
+    if (!texture->packedSurface.mSurface)
+        return false;
+    // Draw the dc's content to the reserved place in the atlas.
+    SkCanvas* canvas = texture->packedSurface.mSurface->getCanvas();
+    const tools::Rectangle& rect = texture->packedSurface.mRect;
+    SkPaint paint;
+    paint.setBlendMode(SkBlendMode::kSrc); // copy as is
+    canvas->drawImageRect(
+        sdc->getAsImage(),
+        SkRect::MakeXYWH(rect.getX(), rect.getY(), rect.GetWidth(), rect.GetHeight()), &paint);
     return true;
 }
 
 void SkiaGlobalWinGlyphCache::Prune()
 {
-    const int MAXSIZE = 64; // TODO
-    if (mLRUOrder.size() > MAXSIZE)
+    std::vector<sk_sp<SkSurface>> aSurfaces = mPackedSurfaceAtlas.ReduceSurfaceNumber(8);
+    if (!aSurfaces.empty())
     {
-        size_t toRemove = mLRUOrder.size() - MAXSIZE;
-        std::vector<uint32_t> idsToRemove(mLRUOrder.begin(), mLRUOrder.begin() + toRemove);
-        mLRUOrder.erase(mLRUOrder.begin(), mLRUOrder.begin() + toRemove);
         for (auto& pWinGlyphCache : maWinGlyphCaches)
-            static_cast<SkiaWinGlyphCache*>(pWinGlyphCache)->RemoveTextures(idsToRemove);
+            static_cast<SkiaWinGlyphCache*>(pWinGlyphCache)->RemoveSurfaces(aSurfaces);
     }
 }
 
-void SkiaGlobalWinGlyphCache::NotifyElementUsed(WinGlyphDrawElement& rElement)
-{
-    SkiaCompatibleDC::Texture* texture
-        = static_cast<SkiaCompatibleDC::Texture*>(rElement.maTexture.get());
-    // make the most recently used
-    auto it = find(mLRUOrder.begin(), mLRUOrder.end(), texture->image->uniqueID());
-    if (it != mLRUOrder.end())
-        mLRUOrder.erase(it);
-    mLRUOrder.push_back(texture->image->uniqueID());
-}
-
-void SkiaWinGlyphCache::RemoveTextures(const std::vector<uint32_t>& idsToRemove)
+void SkiaWinGlyphCache::RemoveSurfaces(const std::vector<sk_sp<SkSurface>>& surfaces)
 {
     auto it = maWinTextureCache.begin();
     while (it != maWinTextureCache.end())
     {
-        assert(dynamic_cast<SkiaCompatibleDC::Texture*>(it->second.maTexture.get()));
-        uint32_t id = static_cast<SkiaCompatibleDC::Texture*>(it->second.maTexture.get())
-                          ->image->uniqueID();
-        if (std::find(idsToRemove.begin(), idsToRemove.end(), id) != idsToRemove.end())
+        assert(dynamic_cast<SkiaCompatibleDC::PackedTexture*>(it->second.maTexture.get()));
+        sk_sp<SkSurface> surface
+            = static_cast<SkiaCompatibleDC::PackedTexture*>(it->second.maTexture.get())
+                  ->packedSurface.mSurface;
+        if (std::find(surfaces.begin(), surfaces.end(), surface) != surfaces.end())
             it = maWinTextureCache.erase(it);
         else
             ++it;