[drape] indexer for glyphs, packing and mapping on texture

4 files changed, 192 insertions, 255 deletions

diff --git a/drape/font_texture.cpp b/drape/font_texture.cpp
index 6b943681e2..a4888c216b 100644
--- a/drape/font_texture.cpp
+++ b/drape/font_texture.cpp
@@ -33,231 +33,144 @@ typedef gray8c_pixel_t const_pixel_t;
 namespace dp
 {
 
-FontTexture::GlyphInfo::GlyphInfo(m2::RectF const & texRect, float xOffset,
-                                  float yOffset, float advance)
-  : ResourceInfo(texRect)
-  , m_xOffset(xOffset)
-  , m_yOffset(yOffset)
-  , m_advance(advance)
+GlyphPacker::GlyphPacker(const m2::PointU & size)
+  : m_size(size)
 {
 }
 
-void FontTexture::GlyphInfo::GetMetrics(float & xOffset, float & yOffset, float & advance) const
+bool GlyphPacker::PackGlyph(uint32_t width, uint32_t height, m2::RectU & rect)
 {
-  xOffset = m_xOffset;
-  yOffset = m_yOffset;
-  advance = m_advance;
-}
+  ASSERT(!IsFull(), ());
+  ASSERT_LESS(width, m_size.x, ());
+  ASSERT_LESS(height, m_size.y, ());
 
-float FontTexture::GlyphInfo::GetAdvance() const
-{
-  return m_advance;
-}
+  if (m_cursor.x + width > m_size.x)
+  {
+    m_cursor.x = 0;
+    m_cursor.y += m_yStep;
+    m_yStep = 0;
+  }
 
-////////////////////////////////////////////////////////////////////////
+  if (m_cursor.y + height > m_size.y)
+  {
+    m_isFull = true;
+    return false;
+  }
 
-Texture::ResourceInfo const * FontTexture::FindResource(Texture::Key const & key) const
-{
-  if (key.GetType() != Texture::Glyph)
-    return NULL;
+  rect = m2::RectU(m_cursor.x, m_cursor.y,
+                   m_cursor.x + width, m_cursor.y + height);
 
-  int unicodePoint = static_cast<GlyphKey const &>(key).GetUnicodePoint();
-  glyph_map_t::const_iterator it = m_glyphs.find(unicodePoint);
-  if (it == m_glyphs.end())
-    return NULL;
+  m_cursor.x += width;
+  m_yStep = max(height, m_yStep);
+  return true;
+}
 
-  return &it->second;
+m2::RectF GlyphPacker::MapTextureCoords(const m2::RectU & pixelRect) const
+{
+  float fWidth = static_cast<float>(m_size.x);
+  float fHeight = static_cast<float>(m_size.y);
+  return m2::RectF(pixelRect.minX() / fWidth,
+                   pixelRect.minY() / fHeight,
+                   pixelRect.maxX() / fWidth,
+                   pixelRect.maxY() / fHeight);
 }
 
-void FontTexture::Add(int unicodePoint, GlyphInfo const & glyphInfo)
+bool GlyphPacker::IsFull() const { return m_isFull; }
+
+GlyphIndex::GlyphIndex(m2::PointU size, RefPointer<GlyphManager> mng)
+  : m_packer(size)
+  , m_mng(mng)
 {
-  m_glyphs.insert(make_pair(unicodePoint, glyphInfo));
 }
 
-namespace
+GlyphInfo const * GlyphIndex::MapResource(GlyphKey const & key)
 {
-  class Grid
+  strings::UniChar uniChar = key.GetUnicodePoint();
+  TResourceMapping::const_iterator it = m_index.find(uniChar);
+  if (it != m_index.end())
+    return it->second.GetRaw();
+
+  GlyphManager::Glyph glyph = m_mng->GetGlyph(uniChar);
+  m2::RectU r;
+  if (!m_packer.PackGlyph(glyph.m_image.m_width, glyph.m_image.m_height, r))
   {
-    typedef pair<m2::RectU, FontTexture *> region_t;
-    typedef vector<region_t> regions_t;
+    glyph.m_image.Destroy();
+    return nullptr;
+  }
 
-  public:
-    void CutTexture(vector<uint8_t> const & image, uint32_t width, uint32_t height)
-    {
-      uint32_t maxTextureSize = Texture::GetMaxTextureSize();
-
-      if (width <= maxTextureSize && width == height)
-        SingleTexture(image, width, height);
-      else
-      {
-        const_view_t srcView = interleaved_view(width, height, (const_pixel_t *)&image[0], width);
-        uint32_t baseSize = maxTextureSize;
-        vector<m2::RectU> notProcessed;
-        notProcessed.push_back(m2::RectU(0, 0, width, height));
-        while (!notProcessed.empty())
-        {
-          vector<m2::RectU> outRects;
-          for (size_t i = 0; i < notProcessed.size(); ++i)
-            CutTextureBySize(srcView, notProcessed[i], baseSize, outRects);
-
-          baseSize >>= 1;
-          swap(notProcessed, outRects);
-        }
-      }
-    }
+  m_pendingNodes.emplace_back(r, glyph);
 
-    void ParseMetrics(string const & fileData)
-    {
-      vector<string> lines;
-      strings::Tokenize(fileData, "\n", MakeBackInsertFunctor(lines));
-      for (size_t i = 0; i < lines.size(); ++i)
-      {
-        vector<string> metrics;
-        strings::Tokenize(lines[i], "\t", MakeBackInsertFunctor(metrics));
-        ASSERT(metrics.size() == 8, ());
-
-        int32_t unicodePoint;
-        int32_t x, y, w, h;
-        double xoff, yoff, advance;
-
-        strings::to_int(metrics[0], unicodePoint);
-        strings::to_int(metrics[1], x);
-        strings::to_int(metrics[2], y);
-        strings::to_int(metrics[3], w);
-        strings::to_int(metrics[4], h);
-        strings::to_double(metrics[5], xoff);
-        strings::to_double(metrics[6], yoff);
-        strings::to_double(metrics[7], advance);
-
-        m2::PointU centerPoint(x + w / 2, y + h / 2);
-        region_t region = GetTexture(centerPoint);
-        FontTexture * texture = region.second;
-        m2::RectU rect = region.first;
-        m2::RectF texRect(texture->GetS(x - rect.minX()), texture->GetT(y - rect.minY()),
-                          texture->GetS(x + w - rect.minX()), texture->GetT(y + h - rect.minY()));
-        texture->Add(unicodePoint, FontTexture::GlyphInfo(texRect, xoff, yoff, advance));
-      }
-    }
+  pair<TResourceMapping::iterator, bool> res = m_index.emplace(uniChar, TResourcePtr(new GlyphInfo(m_packer.MapTextureCoords(r), glyph.m_metrics)));
+  if (!res.second)
+    return nullptr;
 
-    void GetTextures(vector<TransferPointer<Texture> > & textures)
-    {
-      textures.reserve(m_regions.size());
-      for (size_t i = 0; i < m_regions.size(); ++i)
-        textures.push_back(MovePointer<Texture>(m_regions[i].second));
-    }
+  return res.first->second.GetRaw();
+}
 
-  private:
-    void SingleTexture(vector<uint8_t> const & image, uint32_t width, uint32_t height)
+void GlyphIndex::UploadResources(RefPointer<Texture> texture)
+{
+  if (m_pendingNodes.empty())
+    return;
+
+  buffer_vector<size_t, 3> ranges;
+  buffer_vector<uint32_t, 2> maxHeights;
+  uint32_t maxHeight = 0;
+  ranges.push_back(0);
+  for (size_t i = 1; i < m_pendingNodes.size(); ++i)
+  {
+    TPendingNode const & prevNode = m_pendingNodes[i - 1];
+    maxHeight = max(maxHeight, prevNode.first.SizeY());
+    TPendingNode const & currentNode = m_pendingNodes[i];
+    if (ranges.size() < 2 && prevNode.first.minY() < currentNode.first.minY())
     {
-      FontTexture * texture = new FontTexture();
-      texture->Create(width, height, ALPHA, MakeStackRefPointer((void *)&image[0]));
-      m_regions.push_back(make_pair(m2::RectU(0, 0, width, height), texture));
+      ranges.push_back(i);
+      maxHeights.push_back(maxHeight);
+      maxHeight = 0;
     }
+  }
+  maxHeights.push_back(maxHeight);
+  ranges.push_back(m_pendingNodes.size());
 
-    void CutTextureBySize(const_view_t const & image, m2::RectU const & fullRect,
-                          uint32_t cutSize, vector<m2::RectU> & notProcessedRects)
-    {
-      uint32_t fullTexInWidth = fullRect.SizeX() / cutSize;
-      uint32_t fullTexInHeight = fullRect.SizeY() / cutSize;
-
-      if (fullTexInWidth == 0 || fullTexInHeight == 0)
-      {
-        notProcessedRects.push_back(fullRect);
-        return;
-      }
-
-      vector<uint8_t> regionImage(cutSize * cutSize, 0);
-      for (uint32_t dy = 0; dy < fullTexInHeight; ++dy)
-      {
-        for (uint32_t dx = 0; dx < fullTexInWidth; ++dx)
-        {
-          uint32_t pxDx = dx * cutSize + fullRect.minX();
-          uint32_t pxDy = dy * cutSize + fullRect.minY();
-          const_view_t subView = subimage_view(image, pxDx, pxDy, cutSize, cutSize);
-
-          view_t dstView = interleaved_view(cutSize, cutSize,
-                                            (pixel_t *)&regionImage[0], cutSize);
-
-          copy_pixels(subView, dstView);
-          FontTexture * texture = new FontTexture();
-          texture->Create(cutSize, cutSize, ALPHA,
-                          MakeStackRefPointer<void>(&regionImage[0]));
-
-          m_regions.push_back(make_pair(m2::RectU(pxDx, pxDy,
-                                                  pxDx + cutSize,
-                                                  pxDy + cutSize),
-                                        texture));
-        }
-      }
-
-      uint32_t downBorder = fullTexInHeight * cutSize;
-      uint32_t rightBorder = fullTexInWidth * cutSize;
-      if (rightBorder == fullRect.SizeX())
-      {
-        ASSERT(downBorder == fullRect.SizeY(), ());
-        return;
-      }
-
-      notProcessedRects.push_back(m2::RectU(rightBorder, 0, fullRect.maxX(), fullRect.maxY()));
-
-      if (downBorder == fullRect.SizeY())
-        return;
-
-      notProcessedRects.push_back(m2::RectU(0, downBorder, rightBorder, fullRect.maxY()));
-    }
+  ASSERT(maxHeights.size() < 3, ());
+  ASSERT(ranges.size() < 4, ());
 
-  private:
-    region_t GetTexture(m2::PointU const & px)
+  for (size_t i = 1; i < ranges.size(); ++i)
+  {
+    size_t startIndex = ranges[i - 1];
+    size_t endIndex = ranges[i];
+    uint32_t height = maxHeights[i - 1];
+    uint32_t width = m_pendingNodes[endIndex].first.maxX() - m_pendingNodes[startIndex].first.maxX();
+    uint32_t byteCount = my::NextPowOf2(height * width);
+    m2::PointU zeroPoint = m_pendingNodes[startIndex].first.LeftBottom();
+
+    SharedBufferManager::shared_buffer_ptr_t buffer = SharedBufferManager::instance().reserveSharedBuffer(byteCount);
+    uint8_t * dstMemory = SharedBufferManager::GetRawPointer(buffer);
+    view_t dstView = interleaved_view(width, height, (pixel_t *)dstMemory, width);
+    for (size_t node = startIndex; node < endIndex; ++node)
     {
-      regions_t::const_iterator it = find_if(m_regions.begin(), m_regions.end(),
-                                             bind(&m2::RectU::IsPointInside,
-                                                  bind(&region_t::first, _1), px));
-
-      ASSERT(it != m_regions.end(), ());
-      return *it;
-    }
+      GlyphManager::Glyph & glyph = m_pendingNodes[node].second;
+      m2::RectU rect = m_pendingNodes[node].first;
+      rect.Offset(-zeroPoint);
 
-  private:
-    regions_t m_regions;
-  };
-}
-
-void LoadFont(string const & resourcePrefix, vector<TransferPointer<Texture> > & textures)
-{
-  string metrics;
-  int w, h, channelCount;
-  vector<uint8_t> imageData;
+      uint32_t w = rect.SizeX();
+      uint32_t h = rect.SizeY();
 
-  try
-  {
-    {
-      ReaderPtr<ModelReader> reader = GetPlatform().GetReader(resourcePrefix + ".png");
-      imageData.resize(reader.Size());
-      reader.Read(0, &imageData[0], imageData.size());
+      ASSERT_EQUAL(glyph.m_image.m_width, w, ());
+      ASSERT_EQUAL(glyph.m_image.m_height, h, ());
 
-      unsigned char * img = stbi_png_load_from_memory(&imageData[0], imageData.size(),
-                                                      &w, &h, &channelCount, 0);
-      CHECK(channelCount == 1, ("Incorrect font texture format"));
+      view_t dstSubView = subimage_view(dstView, rect.minX(), rect.minY(), w, h);
+      uint8_t * srcMemory = SharedBufferManager::GetRawPointer(glyph.m_image.m_data);
+      const_view_t srcView = interleaved_view(w, h, (const_pixel_t *)srcMemory, w);
 
-      imageData.resize(w * h);
-      memcpy(&imageData[0], img, w * h);
-      stbi_image_free(img);
+      copy_pixels(srcView, dstSubView);
+      glyph.m_image.Destroy();
     }
 
-    {
-      ReaderPtr<ModelReader> reader = GetPlatform().GetReader(resourcePrefix + ".fdf");
-      reader.ReadAsString(metrics);
-    }
-  }
-  catch (RootException & e)
-  {
-    LOG(LERROR, (e.what()));
+    texture->UploadData(zeroPoint.x, zeroPoint.y, width, height, dp::ALPHA, MakeStackRefPointer<void>(dstMemory));
+    SharedBufferManager::instance().freeSharedBuffer(byteCount, buffer);
   }
 
-  Grid grid;
-  grid.CutTexture(imageData, w, h);
-  grid.ParseMetrics(metrics);
-  grid.GetTextures(textures);
+  m_pendingNodes.clear();
 }
 
 } // namespace dp
diff --git a/drape/font_texture.hpp b/drape/font_texture.hpp
index b467348b56..1a044ade85 100644
--- a/drape/font_texture.hpp
+++ b/drape/font_texture.hpp
@@ -2,6 +2,7 @@
 
 #include "pointers.hpp"
 #include "texture.hpp"
+#include "glyph_manager.hpp"
 
 #include "../std/map.hpp"
 #include "../std/vector.hpp"
@@ -10,46 +11,74 @@
 namespace dp
 {
 
-class FontTexture : public Texture
+class GlyphPacker
 {
 public:
-  class GlyphKey : public Key
-  {
-  public:
-    GlyphKey(int32_t unicode) : m_unicode(unicode) {}
+  GlyphPacker(m2::PointU const & size);
 
-    ResourceType GetType() const { return Texture::Glyph; }
-    int32_t GetUnicodePoint() const { return m_unicode; }
+  bool PackGlyph(uint32_t width, uint32_t height, m2::RectU & rect);
+  m2::RectF MapTextureCoords(m2::RectU const & pixelRect) const;
+  bool IsFull() const;
 
-  private:
-    int32_t m_unicode;
-  };
+private:
+  m2::PointU m_size = m2::PointU(0, 0);
+  m2::PointU m_cursor = m2::PointU(0, 0);
+  uint32_t m_yStep = 0;
+  bool m_isFull = false;
+};
 
-  class GlyphInfo : public ResourceInfo
-  {
-  public:
-    GlyphInfo(m2::RectF const & texRect, float xOffset,
-              float yOffset, float advance);
+class GlyphKey : public Texture::Key
+{
+public:
+  GlyphKey(strings::UniChar unicodePoint) : m_unicodePoint(unicodePoint) {}
 
-    virtual ResourceType GetType() const { return Texture::Glyph; }
-    void GetMetrics(float & xOffset, float & yOffset, float & advance) const;
-    float GetAdvance() const;
+  Texture::ResourceType GetType() const { return Texture::Glyph; }
+  strings::UniChar GetUnicodePoint() const { return m_unicodePoint; }
 
-  private:
-    float m_xOffset, m_yOffset;
-    float m_advance;
-  };
+private:
+  strings::UniChar m_unicodePoint;
+};
 
+class GlyphInfo : public Texture::ResourceInfo
+{
+  typedef Texture::ResourceInfo TBase;
 public:
-  ResourceInfo const * FindResource(Key const & key) const;
+  GlyphInfo(m2::RectF const & texRect, GlyphManager::GlyphMetrics const & metrics)
+    : TBase(texRect)
+    , m_metrics(metrics)
+  {
+  }
 
-  void Add(int unicodePoint, GlyphInfo const & glyphInfo);
+  virtual Texture::ResourceType GetType() const { return Texture::Glyph; }
+  GlyphManager::GlyphMetrics const & GetMetrics() const { return m_metrics; }
 
 private:
-  typedef map<int, GlyphInfo> glyph_map_t;
-  glyph_map_t m_glyphs;
+  GlyphManager::GlyphMetrics m_metrics;
 };
 
-void LoadFont(string const & resourcePrefix, vector<TransferPointer<Texture> > & textures);
+class GlyphIndex
+{
+public:
+  GlyphIndex(m2::PointU size, RefPointer<GlyphManager> mng);
+
+  /// can return nullptr
+  GlyphInfo const * MapResource(GlyphKey const & key);
+  void UploadResources(RefPointer<Texture> texture);
+
+  glConst GetMinFilter() const { return gl_const::GLLinear; }
+  glConst GetMagFilter() const { return gl_const::GLLinear; }
+
+private:
+  GlyphPacker m_packer;
+  RefPointer<GlyphManager> m_mng;
+
+  typedef MasterPointer<GlyphInfo> TResourcePtr;
+  typedef map<strings::UniChar, TResourcePtr> TResourceMapping;
+  typedef pair<m2::RectU, GlyphManager::Glyph> TPendingNode;
+  typedef vector<TPendingNode> TPendingNodes;
+
+  TResourceMapping m_index;
+  TPendingNodes m_pendingNodes;
+};
 
 }
diff --git a/drape/glyph_manager.cpp b/drape/glyph_manager.cpp
index a656392062..a4789580c6 100644
--- a/drape/glyph_manager.cpp
+++ b/drape/glyph_manager.cpp
@@ -194,8 +194,7 @@ public:
     {
       imgWidth,
       imgHeigh,
-      data,
-      bufferSize
+      data
     };
 
     result.m_metrics = GlyphManager::GlyphMetrics
@@ -296,6 +295,7 @@ struct GlyphManager::Impl
 {
   FT_Library m_library;
   TUniBlocks m_blocks;
+  TUniBlockIter m_lastUsedBlock;
   vector<Font> m_fonts;
 
   uint32_t m_baseGlyphHeight;
@@ -419,6 +419,8 @@ GlyphManager::GlyphManager(GlyphManager::Params const & params)
       uniBlock.m_fontsWeight.back() = node.second;
     }
   }
+
+  m_impl->m_lastUsedBlock = m_impl->m_blocks.end();
 }
 
 GlyphManager::~GlyphManager()
@@ -430,13 +432,12 @@ GlyphManager::~GlyphManager()
   delete m_impl;
 }
 
-void GlyphManager::GetGlyphs(vector<strings::UniChar> const & unicodePoints, vector<GlyphManager::Glyph> & glyphs)
+GlyphManager::Glyph GlyphManager::GetGlyph(strings::UniChar unicodePoint)
 {
-  glyphs.reserve(unicodePoints.size());
-
   TUniBlockIter iter = m_impl->m_blocks.end();
-  int fontIndex = -1;
-  for (strings::UniChar const & unicodePoint : unicodePoints)
+  if (m_impl->m_lastUsedBlock != m_impl->m_blocks.end() && m_impl->m_lastUsedBlock->HasSymbol(unicodePoint))
+    iter = m_impl->m_lastUsedBlock;
+  else
   {
     if (iter == m_impl->m_blocks.end() || !iter->HasSymbol(unicodePoint))
     {
@@ -445,39 +446,34 @@ void GlyphManager::GetGlyphs(vector<strings::UniChar> const & unicodePoints, vec
       {
         return block.m_end < v;
       });
-      fontIndex = -1;
     }
+  }
 
-    if (iter == m_impl->m_blocks.end())
-    {
-      glyphs.push_back(GetInvalidGlyph());
-      continue;
-    }
+  if (iter == m_impl->m_blocks.end())
+    return GetInvalidGlyph();
 
-    UnicodeBlock const & block = *iter;
-    ASSERT(block.HasSymbol(unicodePoint), ());
-    do
+  m_impl->m_lastUsedBlock = iter;
+
+  int fontIndex = -1;
+  UnicodeBlock const & block = *iter;
+  ASSERT(block.HasSymbol(unicodePoint), ());
+  do
+  {
+    if (fontIndex != -1)
     {
-      if (fontIndex != -1)
-      {
-        ASSERT_LESS(fontIndex, m_impl->m_fonts.size(), ());
-        Font const & f = m_impl->m_fonts[fontIndex];
-        if (f.HasGlyph(unicodePoint))
-        {
-          glyphs.push_back(f.GetGlyph(unicodePoint, m_impl->m_baseGlyphHeight));
-          break;
-        }
-      }
+      ASSERT_LESS(fontIndex, m_impl->m_fonts.size(), ());
+      Font const & f = m_impl->m_fonts[fontIndex];
+      if (f.HasGlyph(unicodePoint))
+        return f.GetGlyph(unicodePoint, m_impl->m_baseGlyphHeight);
+    }
 
-      fontIndex = block.GetFontOffset(fontIndex);
-    } while(fontIndex != -1);
+    fontIndex = block.GetFontOffset(fontIndex);
+  } while(fontIndex != -1);
 
-    if (fontIndex == -1)
-      glyphs.push_back(GetInvalidGlyph());
-  }
+  return GetInvalidGlyph();
 }
 
-GlyphManager::Glyph const & GlyphManager::GetInvalidGlyph() const
+GlyphManager::Glyph GlyphManager::GetInvalidGlyph() const
 {
   static bool s_inited = false;
   static Glyph s_glyph;
diff --git a/drape/glyph_manager.hpp b/drape/glyph_manager.hpp
index 2c8b1fbc96..6b14e4f156 100644
--- a/drape/glyph_manager.hpp
+++ b/drape/glyph_manager.hpp
@@ -43,14 +43,13 @@ public:
 
     void Destroy()
     {
-      SharedBufferManager::instance().freeSharedBuffer(m_bufferSize, m_data);
+      SharedBufferManager::instance().freeSharedBuffer(m_data->size(), m_data);
     }
 
     int m_width;
     int m_height;
 
     SharedBufferManager::shared_buffer_ptr_t m_data;
-    size_t m_bufferSize;
   };
 
   struct Glyph
@@ -62,10 +61,10 @@ public:
   GlyphManager(Params const & params);
   ~GlyphManager();
 
-  void GetGlyphs(vector<strings::UniChar> const & unicodePoints, vector<Glyph> & glyphs);
+  Glyph GetGlyph(strings::UniChar unicodePoints);
 
 private:
-  Glyph const & GetInvalidGlyph() const;
+  Glyph GetInvalidGlyph() const;
 
 private:
   struct Impl;