Overlay tree optimization

6 files changed, 139 insertions, 77 deletions

diff --git a/drape/overlay_handle.cpp b/drape/overlay_handle.cpp
index d656048c6e..761da448fd 100644
--- a/drape/overlay_handle.cpp
+++ b/drape/overlay_handle.cpp
@@ -34,7 +34,16 @@ OverlayHandle::OverlayHandle(FeatureID const & id,
   , m_pivotZ(0.0)
   , m_isBillboard(isBillboard)
   , m_isVisible(false)
+  , m_enableCaching(false)
+  , m_extendedRectsDirty(true)
+  , m_extendedRectDirty(true)
+{}
+
+void OverlayHandle::SetCachingEnable(bool enable)
 {
+  m_enableCaching = enable;
+  m_extendedRectsDirty = true;
+  m_extendedRectDirty = true;
 }
 
 bool OverlayHandle::IsVisible() const
@@ -76,11 +85,8 @@ m2::PointD OverlayHandle::GetPivot(ScreenBase const & screen, bool perspective)
 
 bool OverlayHandle::IsIntersect(ScreenBase const & screen, ref_ptr<OverlayHandle> const h) const
 {
-  Rects ar1;
-  Rects ar2;
-
-  GetExtendedPixelShape(screen, ar1);
-  h->GetExtendedPixelShape(screen, ar2);
+  Rects const & ar1 = GetExtendedPixelShape(screen);
+  Rects const & ar2 = h->GetExtendedPixelShape(screen);
 
   for (size_t i = 0; i < ar1.size(); ++i)
     for (size_t j = 0; j < ar2.size(); ++j)
@@ -102,11 +108,9 @@ void OverlayHandle::GetElementIndexes(ref_ptr<IndexBufferMutator> mutator) const
   mutator->AppendIndexes(m_indexes.GetRawConst(), m_indexes.Size());
 }
 
-void OverlayHandle::GetAttributeMutation(ref_ptr<AttributeBufferMutator> mutator,
-                                         ScreenBase const & screen) const
+void OverlayHandle::GetAttributeMutation(ref_ptr<AttributeBufferMutator> mutator) const
 {
   UNUSED_VALUE(mutator);
-  UNUSED_VALUE(screen);
 }
 
 bool OverlayHandle::HasDynamicAttributes() const
@@ -140,16 +144,26 @@ OverlayHandle::TOffsetNode const & OverlayHandle::GetOffsetNode(uint8_t bufferID
 
 m2::RectD OverlayHandle::GetExtendedPixelRect(ScreenBase const & screen) const
 {
-  m2::RectD rect = GetPixelRect(screen, screen.isPerspective());
-  rect.Inflate(m_extendingSize, m_extendingSize);
-  return rect;
+  if (m_enableCaching && !m_extendedRectDirty)
+    return m_extendedRectCache;
+
+  m_extendedRectCache = GetPixelRect(screen, screen.isPerspective());
+  m_extendedRectCache.Inflate(m_extendingSize, m_extendingSize);
+  m_extendedRectDirty = false;
+  return m_extendedRectCache;
 }
 
-void OverlayHandle::GetExtendedPixelShape(ScreenBase const & screen, Rects & rects) const
+OverlayHandle::Rects const & OverlayHandle::GetExtendedPixelShape(ScreenBase const & screen) const
 {
-  GetPixelShape(screen, rects, screen.isPerspective());
-  for (auto & rect : rects)
+  if (m_enableCaching && !m_extendedRectsDirty)
+    return m_extendedRectsCache;
+
+  m_extendedRectsCache.clear();
+  GetPixelShape(screen, m_extendedRectsCache, screen.isPerspective());
+  for (auto & rect : m_extendedRectsCache)
     rect.Inflate(m_extendingSize, m_extendingSize);
+  m_extendedRectsDirty = false;
+  return m_extendedRectsCache;
 }
 
 m2::RectD OverlayHandle::GetPerspectiveRect(m2::RectD const & pixelRect, ScreenBase const & screen) const
diff --git a/drape/overlay_handle.hpp b/drape/overlay_handle.hpp
index 0553891a60..83874ba4ba 100644
--- a/drape/overlay_handle.hpp
+++ b/drape/overlay_handle.hpp
@@ -64,15 +64,14 @@ public:
   double GetExtendingSize() const { return m_extendingSize; }
   void SetExtendingSize(double extendingSize) { m_extendingSize = extendingSize; }
   m2::RectD GetExtendedPixelRect(ScreenBase const & screen) const;
-  void GetExtendedPixelShape(ScreenBase const & screen, Rects & rects) const;
+  Rects const & GetExtendedPixelShape(ScreenBase const & screen) const;
 
   bool IsIntersect(ScreenBase const & screen, ref_ptr<OverlayHandle> const h) const;
 
   virtual bool IndexesRequired() const { return true; }
   void * IndexStorage(uint32_t size);
   void GetElementIndexes(ref_ptr<IndexBufferMutator> mutator) const;
-  virtual void GetAttributeMutation(ref_ptr<AttributeBufferMutator> mutator,
-                                    ScreenBase const & screen) const;
+  virtual void GetAttributeMutation(ref_ptr<AttributeBufferMutator> mutator) const;
 
   bool HasDynamicAttributes() const;
   void AddDynamicAttribute(BindingInfo const & binding, uint32_t offset, uint32_t count);
@@ -90,6 +89,8 @@ public:
   int GetOverlayRank() const { return m_overlayRank; }
   void SetOverlayRank(int overlayRank) { m_overlayRank = overlayRank; }
 
+  void SetCachingEnable(bool enable);
+
 #ifdef DEBUG_OVERLAYS_OUTPUT
   virtual string GetOverlayDebugInfo() { return ""; }
 #endif
@@ -125,6 +126,12 @@ private:
   struct OffsetNodeFinder;
 
   set<TOffsetNode, LessOffsetNode> m_offsets;
+
+  bool m_enableCaching;
+  mutable Rects m_extendedRectsCache;
+  mutable bool m_extendedRectsDirty;
+  mutable m2::RectD m_extendedRectCache;
+  mutable bool m_extendedRectDirty;
 };
 
 class SquareHandle : public OverlayHandle
diff --git a/drape/overlay_tree.cpp b/drape/overlay_tree.cpp
index b27bc4074c..cfc3fd401d 100644
--- a/drape/overlay_tree.cpp
+++ b/drape/overlay_tree.cpp
@@ -7,7 +7,6 @@ namespace dp
 {
 
 int const kFrameUpdarePeriod = 10;
-int const kFrameUpdarePeriodIn3d = 30;
 int const kAverageHandlesCount[dp::OverlayRanksCount] = { 300, 200, 50 };
 
 namespace
@@ -67,13 +66,13 @@ OverlayTree::OverlayTree()
     m_handles[i].reserve(kAverageHandlesCount[i]);
 }
 
-bool OverlayTree::Frame(bool is3d)
+bool OverlayTree::Frame()
 {
   if (IsNeedUpdate())
     return true;
 
   m_frameCounter++;
-  if (m_frameCounter >= (is3d ? kFrameUpdarePeriodIn3d : kFrameUpdarePeriod))
+  if (m_frameCounter >= kFrameUpdarePeriod)
     m_frameCounter = -1;
 
   return IsNeedUpdate();
@@ -84,15 +83,11 @@ bool OverlayTree::IsNeedUpdate() const
   return m_frameCounter == -1;
 }
 
-void OverlayTree::ForceUpdate()
-{
-  m_frameCounter = -1;
-}
-
 void OverlayTree::StartOverlayPlacing(ScreenBase const & screen)
 {
   ASSERT(IsNeedUpdate(), ());
   Clear();
+  m_handlesCache.clear();
   m_traits.m_modelView = screen;
 
 #ifdef COLLECT_DISPLACEMENT_INFO
@@ -100,6 +95,15 @@ void OverlayTree::StartOverlayPlacing(ScreenBase const & screen)
 #endif
 }
 
+void OverlayTree::Remove(ref_ptr<OverlayHandle> handle)
+{
+  if (m_frameCounter == -1)
+    return;
+
+  if (m_handlesCache.find(GetHandleKey(handle)) != m_handlesCache.end())
+    m_frameCounter = -1;
+}
+
 void OverlayTree::Add(ref_ptr<OverlayHandle> handle)
 {
   ASSERT(IsNeedUpdate(), ());
@@ -107,6 +111,10 @@ void OverlayTree::Add(ref_ptr<OverlayHandle> handle)
   ScreenBase const & modelView = GetModelView();
 
   handle->SetIsVisible(false);
+  handle->SetCachingEnable(true);
+
+  if (m_handlesCache.find(GetHandleKey(handle)) != m_handlesCache.end())
+    return;
 
   if (!handle->Update(modelView))
     return;
@@ -191,7 +199,7 @@ void OverlayTree::InsertHandle(ref_ptr<OverlayHandle> handle,
       // Handle is displaced and bound to its parent, parent will be displaced too.
       if (boundToParent)
       {
-        Erase(parentOverlay);
+        DeleteHandle(parentOverlay);
 
       #ifdef DEBUG_OVERLAYS_OUTPUT
         LOG(LINFO, ("Displace (0):", handle->GetOverlayDebugInfo(), "->", parentOverlay->GetOverlayDebugInfo()));
@@ -219,25 +227,51 @@ void OverlayTree::InsertHandle(ref_ptr<OverlayHandle> handle,
 
   // Current overlay displaces other overlay, delete them.
   for (auto const & rivalHandle : rivals)
-    AddHandleToDelete(rivalHandle);
-
-  for (auto const & handleToDelete : m_handlesToDelete)
   {
-    Erase(handleToDelete);
+    if (rivalHandle->IsBound())
+    {
+      // Delete rival handle and all handles bound to it.
+      for (auto it = m_handlesCache.begin(); it != m_handlesCache.end();)
+      {
+        if (it->second->GetFeatureID() == rivalHandle->GetFeatureID())
+        {
+          Erase(it->second);
 
-  #ifdef DEBUG_OVERLAYS_OUTPUT
-    LOG(LINFO, ("Displace (2):", handle->GetOverlayDebugInfo(), "->", handleToDelete->GetOverlayDebugInfo()));
-  #endif
+        #ifdef DEBUG_OVERLAYS_OUTPUT
+          LOG(LINFO, ("Displace (2):", handle->GetOverlayDebugInfo(), "->", it->second->GetOverlayDebugInfo()));
+        #endif
 
-  #ifdef COLLECT_DISPLACEMENT_INFO
-    m_displacementInfo.emplace_back(DisplacementData(handle->GetExtendedPixelRect(modelView).Center(),
-                                                     handleToDelete->GetExtendedPixelRect(modelView).Center(),
-                                                     dp::Color(0, 0, 255, 255)));
-  #endif
-  }
+        #ifdef COLLECT_DISPLACEMENT_INFO
+          m_displacementInfo.emplace_back(DisplacementData(handle->GetExtendedPixelRect(modelView).Center(),
+                                                           it->second->GetExtendedPixelRect(modelView).Center(),
+                                                           dp::Color(0, 0, 255, 255)));
+        #endif
+
+          it = m_handlesCache.erase(it);
+        }
+        else
+        {
+          ++it;
+        }
+      }
+    }
+    else
+    {
+      DeleteHandle(rivalHandle);
+
+    #ifdef DEBUG_OVERLAYS_OUTPUT
+      LOG(LINFO, ("Displace (3):", handle->GetOverlayDebugInfo(), "->", handleToDelete->GetOverlayDebugInfo()));
+    #endif
 
-  m_handlesToDelete.clear();
+    #ifdef COLLECT_DISPLACEMENT_INFO
+      m_displacementInfo.emplace_back(DisplacementData(handle->GetExtendedPixelRect(modelView).Center(),
+                                                       rivalHandle->GetExtendedPixelRect(modelView).Center(),
+                                                       dp::Color(0, 0, 255, 255)));
+    #endif
+    }
+  }
 
+  m_handlesCache.insert(make_pair(GetHandleKey(handle), handle));
   TBase::Add(handle, pixelRect);
 }
 
@@ -266,10 +300,11 @@ void OverlayTree::EndOverlayPlacing()
     m_handles[rank].clear();
   }
 
-  ForEach([] (ref_ptr<OverlayHandle> const & h)
+  for (auto it = m_handlesCache.begin(); it != m_handlesCache.end(); ++it)
   {
-    h->SetIsVisible(true);
-  });
+    it->second->SetIsVisible(true);
+    it->second->SetCachingEnable(false);
+  }
 
   m_frameCounter = 0;
 
@@ -285,37 +320,30 @@ bool OverlayTree::CheckHandle(ref_ptr<OverlayHandle> handle, int currentRank,
     return true;
 
   int const seachingRank = currentRank - 1;
-  return FindNode([&](ref_ptr<OverlayHandle> const & h) -> bool
+  for (auto it = m_handlesCache.begin(); it != m_handlesCache.end(); ++it)
   {
-    if (h->GetFeatureID() == handle->GetFeatureID() && h->GetOverlayRank() == seachingRank)
+    if (it->second->GetFeatureID() == handle->GetFeatureID() &&
+        it->second->GetOverlayRank() == seachingRank)
     {
-      parentOverlay = h;
+      parentOverlay = it->second;
       return true;
     }
-    return false;
-  });
+  }
+
+  return false;
 }
 
-void OverlayTree::AddHandleToDelete(ref_ptr<OverlayHandle> const & handle)
+void OverlayTree::DeleteHandle(ref_ptr<OverlayHandle> const & handle)
 {
-  if (handle->IsBound())
-  {
-    ForEach([&](ref_ptr<OverlayHandle> const & h)
-    {
-      if (h->GetFeatureID() == handle->GetFeatureID())
-      {
-        if (find(m_handlesToDelete.begin(),
-                 m_handlesToDelete.end(), h) == m_handlesToDelete.end())
-          m_handlesToDelete.push_back(h);
-      }
-    });
-  }
-  else
-  {
-    if (find(m_handlesToDelete.begin(),
-             m_handlesToDelete.end(), handle) == m_handlesToDelete.end())
-      m_handlesToDelete.push_back(handle);
-  }
+  size_t const deletedCount = m_handlesCache.erase(GetHandleKey(handle));
+  ASSERT_NOT_EQUAL(deletedCount, 0, ());
+  if (deletedCount != 0)
+    Erase(handle);
+}
+
+uint64_t OverlayTree::GetHandleKey(ref_ptr<OverlayHandle> const & handle) const
+{
+  return reinterpret_cast<uint64_t>(handle.get());
 }
 
 void OverlayTree::Select(m2::PointD const & glbPoint, TOverlayContainer & result) const
@@ -327,11 +355,11 @@ void OverlayTree::Select(m2::PointD const & glbPoint, TOverlayContainer & result
   m2::RectD rect(pxPoint, pxPoint);
   rect.Inflate(kSearchRectHalfSize, kSearchRectHalfSize);
 
-  ForEach([&](ref_ptr<OverlayHandle> const & h)
+  for (auto it = m_handlesCache.begin(); it != m_handlesCache.end(); ++it)
   {
-    if (rect.IsPointInside(h->GetPivot(screen, false)))
-      result.push_back(h);
-  });
+    if (rect.IsPointInside(it->second->GetPivot(screen, false)))
+      result.push_back(it->second);
+  }
 }
 
 void OverlayTree::Select(m2::RectD const & rect, TOverlayContainer & result) const
diff --git a/drape/overlay_tree.hpp b/drape/overlay_tree.hpp
index d56ef3b43f..878bd1938b 100644
--- a/drape/overlay_tree.hpp
+++ b/drape/overlay_tree.hpp
@@ -9,6 +9,7 @@
 
 #include "std/array.hpp"
 #include "std/vector.hpp"
+#include "std/unordered_map.hpp"
 
 namespace dp
 {
@@ -39,12 +40,12 @@ class OverlayTree : public m4::Tree<ref_ptr<OverlayHandle>, detail::OverlayTrait
 public:
   OverlayTree();
 
-  bool Frame(bool is3d);
+  bool Frame();
   bool IsNeedUpdate() const;
-  void ForceUpdate();
 
   void StartOverlayPlacing(ScreenBase const & screen);
   void Add(ref_ptr<OverlayHandle> handle);
+  void Remove(ref_ptr<OverlayHandle> handle);
   void EndOverlayPlacing();
 
   void Select(m2::RectD const & rect, TOverlayContainer & result) const;
@@ -72,11 +73,16 @@ private:
                     ref_ptr<OverlayHandle> const & parentOverlay);
   bool CheckHandle(ref_ptr<OverlayHandle> handle, int currentRank,
                    ref_ptr<OverlayHandle> & parentOverlay) const;
-  void AddHandleToDelete(ref_ptr<OverlayHandle> const & handle);
+  void DeleteHandle(ref_ptr<OverlayHandle> const & handle);
+
+  uint64_t GetHandleKey(ref_ptr<OverlayHandle> const & handle) const;
 
   int m_frameCounter;
   array<vector<ref_ptr<OverlayHandle>>, dp::OverlayRanksCount> m_handles;
   vector<ref_ptr<OverlayHandle>> m_handlesToDelete;
+
+  unordered_map<uint64_t, ref_ptr<OverlayHandle>> m_handlesCache;
+
   bool m_followingMode;
 
 #ifdef COLLECT_DISPLACEMENT_INFO
diff --git a/drape/render_bucket.cpp b/drape/render_bucket.cpp
index 830b9dc0c5..fefe6f8029 100644
--- a/drape/render_bucket.cpp
+++ b/drape/render_bucket.cpp
@@ -71,7 +71,13 @@ void RenderBucket::CollectOverlayHandles(ref_ptr<OverlayTree> tree)
     tree->Add(make_ref(overlayHandle));
 }
 
-void RenderBucket::Render(ScreenBase const & screen)
+void RenderBucket::RemoveOverlayHandles(ref_ptr<OverlayTree> tree)
+{
+  for (drape_ptr<OverlayHandle> const & overlayHandle : m_overlay)
+    tree->Remove(make_ref(overlayHandle));
+}
+
+void RenderBucket::Render()
 {
   ASSERT(m_buffer != nullptr, ());
 
@@ -94,7 +100,7 @@ void RenderBucket::Render(ScreenBase const & screen)
       }
 
       if (handle->HasDynamicAttributes())
-        handle->GetAttributeMutation(rfpAttrib, screen);
+        handle->GetAttributeMutation(rfpAttrib);
     }
 
     m_buffer->ApplyMutation(hasIndexMutation ? rfpIndex : nullptr, rfpAttrib);
diff --git a/drape/render_bucket.hpp b/drape/render_bucket.hpp
index c66e51be72..c2837a96d1 100644
--- a/drape/render_bucket.hpp
+++ b/drape/render_bucket.hpp
@@ -36,7 +36,8 @@ public:
 
   void Update(ScreenBase const & modelView);
   void CollectOverlayHandles(ref_ptr<OverlayTree> tree);
-  void Render(ScreenBase const & screen);
+  void RemoveOverlayHandles(ref_ptr<OverlayTree> tree);
+  void Render();
 
   // Only for testing! Don't use this function in production code!
   void RenderDebug(ScreenBase const & screen) const;