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>

3 files changed, 208 insertions, 29 deletions

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;