[drape] overlay tree for displacment overlay elements

5 files changed, 173 insertions, 11 deletions

diff --git a/drape/drape_common.pri b/drape/drape_common.pri
index 93bec0591c..5569f00037 100644
--- a/drape/drape_common.pri
+++ b/drape/drape_common.pri
@@ -31,7 +31,8 @@ SOURCES += \
     $$DRAPE_DIR/render_bucket.cpp \
     $$DRAPE_DIR/overlay_handle.cpp \
     $$DRAPE_DIR/index_buffer_mutator.cpp \
-    $$DRAPE_DIR/batcher_helpers.cpp
+    $$DRAPE_DIR/batcher_helpers.cpp \
+    $$DRAPE_DIR/overlay_tree.cpp
 
 HEADERS += \
     $$DRAPE_DIR/data_buffer.hpp \
@@ -68,4 +69,5 @@ HEADERS += \
     $$DRAPE_DIR/render_bucket.hpp \
     $$DRAPE_DIR/overlay_handle.hpp \
     $$DRAPE_DIR/index_buffer_mutator.hpp \
-    $$DRAPE_DIR/batcher_helpers.hpp
+    $$DRAPE_DIR/batcher_helpers.hpp \
+    $$DRAPE_DIR/overlay_tree.hpp
diff --git a/drape/overlay_tree.cpp b/drape/overlay_tree.cpp
new file mode 100644
index 0000000000..b184c5b6b3
--- /dev/null
+++ b/drape/overlay_tree.cpp
@@ -0,0 +1,94 @@
+#include "overlay_tree.hpp"
+
+#include "../std/bind.hpp"
+
+void OverlayTree::StartOverlayPlacing(const ScreenBase & screen)
+{
+  m_modelView = screen;
+  ASSERT(m_tree.empty(), ());
+}
+
+void OverlayTree::Add(RefPointer<OverlayHandle> handle)
+{
+  handle->SetIsVisible(false);
+  m2::RectD pixelRect = handle->GetPixelRect(m_modelView);
+  
+  find_result_t elements;
+  FindIntersectedFunctor f(pixelRect, elements);
+  m_tree.for_each(f);
+
+  double inputPriority = handle->GetPriority();
+  for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it)
+  {
+    if (inputPriority < (*it)->m_nodeValue->GetPriority())
+      return;
+  }
+
+  for (find_result_t::const_iterator it = elements.begin(); it != elements.end(); ++it)
+    m_tree.erase(*(*it));
+
+  m_tree.insert(Node(handle, pixelRect));
+}
+
+void OverlayTree::EndOverlayPlacing()
+{
+  for (tree_t::const_iterator it = m_tree.begin(); it != m_tree.end(); ++it)
+  {
+    RefPointer<OverlayHandle> handle = (*it).m_nodeValue;
+    handle->SetIsVisible(true);
+  }
+  m_tree.clear();
+}
+
+////////////////////////////////////////////////
+OverlayTree::Node::Node(RefPointer<OverlayHandle> handle,
+                        m2::RectD const & pixelRect)
+  : m_nodeValue(handle)
+{
+  m_pts[0] = pixelRect.minX();
+  m_pts[1] = pixelRect.minY();
+  m_pts[2] = pixelRect.maxX();
+  m_pts[3] = pixelRect.maxY();
+}
+
+OverlayTree::BaseFindFunctor::BaseFindFunctor(m2::RectD const & r)
+  : m_rect(r)
+{
+}
+
+bool OverlayTree::BaseFindFunctor::ScanLeft(size_t plane, Node const & v) const
+{
+  switch (plane & 3)    // % 4
+  {
+  case 2: return m_rect.minX() < v[2];
+  case 3: return m_rect.minY() < v[3];
+  default: return true;
+  }
+}
+
+bool OverlayTree::BaseFindFunctor::ScanRight(size_t plane, Node const & v) const
+{
+  switch (plane & 3)  // % 4
+  {
+  case 0: return m_rect.maxX() > v[0];
+  case 1: return m_rect.maxY() > v[1];
+  default: return true;
+  }
+}
+
+OverlayTree::FindIntersectedFunctor::FindIntersectedFunctor(m2::RectD const & r,
+                                                            find_result_t & intersections)
+  : base_t(r)
+  , m_intersections(intersections)
+{
+}
+
+void OverlayTree::FindIntersectedFunctor::operator()(OverlayTree::Node const & node)
+{
+  m2::RectD const & r = base_t::m_rect;
+
+  bool isIntersect = !((node.m_pts[2] <= r.minX()) || (node.m_pts[0] >= r.maxX()) ||
+      (node.m_pts[3] <= r.minY()) || (node.m_pts[1] >= r.maxY()));
+  if (isIntersect)
+    m_intersections.push_back(&node);
+}
diff --git a/drape/overlay_tree.hpp b/drape/overlay_tree.hpp
new file mode 100644
index 0000000000..5e9bb5207d
--- /dev/null
+++ b/drape/overlay_tree.hpp
@@ -0,0 +1,60 @@
+#pragma once
+
+#include "overlay_handle.hpp"
+
+#include "../base/buffer_vector.hpp"
+#include "../geometry/screenbase.hpp"
+
+#include "../std/kdtree.hpp"
+
+class OverlayTree
+{
+public:
+  void StartOverlayPlacing(ScreenBase const & screen);
+  void Add(RefPointer<OverlayHandle> handle);
+  void EndOverlayPlacing();
+
+private:
+  struct Node
+  {
+    typedef double value_type;
+
+    Node(RefPointer<OverlayHandle> handle, m2::RectD const & pixelRect);
+
+    RefPointer<OverlayHandle> m_nodeValue;
+    double m_pts[4];
+
+    double operator[] (size_t i) const { return m_pts[i]; }
+  };
+
+  ScreenBase m_modelView;
+  typedef KDTree::KDTree<4, Node> tree_t;
+  tree_t m_tree;
+
+private:
+  typedef buffer_vector<Node const *, 8> find_result_t;
+
+  class BaseFindFunctor
+  {
+  public:
+    BaseFindFunctor(m2::RectD const & r);
+
+    bool ScanLeft(size_t plane, Node const & v) const;
+    bool ScanRight(size_t plane, Node const & v) const;
+
+  protected:
+    m2::RectD const & m_rect;
+  };
+
+  class FindIntersectedFunctor : public BaseFindFunctor
+  {
+    typedef BaseFindFunctor base_t;
+  public:
+    FindIntersectedFunctor(m2::RectD const & r, find_result_t & intersections);
+
+    void operator()(Node const & node);
+
+  private:
+    find_result_t & m_intersections;
+  };
+};
diff --git a/drape/render_bucket.cpp b/drape/render_bucket.cpp
index dcc91aa1e3..ea80a47562 100644
--- a/drape/render_bucket.cpp
+++ b/drape/render_bucket.cpp
@@ -1,5 +1,9 @@
 #include "render_bucket.hpp"
 
+#include "overlay_handle.hpp"
+#include "vertex_array_buffer.hpp"
+#include "overlay_tree.hpp"
+
 #include "../base/stl_add.hpp"
 #include "../std/bind.hpp"
 
@@ -24,17 +28,18 @@ void RenderBucket::AddOverlayHandle(TransferPointer<OverlayHandle> handle)
   m_overlay.push_back(MasterPointer<OverlayHandle>(handle));
 }
 
-void RenderBucket::CollectOverlayHandles()
+void RenderBucket::CollectOverlayHandles(RefPointer<OverlayTree> tree)
 {
-
+  for_each(m_overlay.begin(), m_overlay.end(), bind(&OverlayTree::Add, tree.GetRaw(),
+                                                    bind(&MasterPointer<OverlayHandle>::GetRefPointer, _1)));
 }
 
 namespace
 {
   void AccumulateIndexes(MasterPointer<OverlayHandle> handle, RefPointer<IndexBufferMutator> mutator)
   {
-    handle->SetIsVisible(true);
-    handle->GetElementIndexes(mutator);
+    if (handle->IsVisible())
+      handle->GetElementIndexes(mutator);
   }
 }
 
diff --git a/drape/render_bucket.hpp b/drape/render_bucket.hpp
index 99719e7551..bcd778167c 100644
--- a/drape/render_bucket.hpp
+++ b/drape/render_bucket.hpp
@@ -1,9 +1,10 @@
 #pragma once
 
-#include "overlay_handle.hpp"
-#include "vertex_array_buffer.hpp"
-#include "uniform_value.hpp"
-#include "uniform_values_storage.hpp"
+#include "pointers.hpp"
+
+class OverlayHandle;
+class OverlayTree;
+class VertexArrayBuffer;
 
 class RenderBucket
 {
@@ -15,7 +16,7 @@ public:
 
   void AddOverlayHandle(TransferPointer<OverlayHandle> handle);
 
-  void CollectOverlayHandles(/*OverlayTree */);
+  void CollectOverlayHandles(RefPointer<OverlayTree> tree);
   void Render();
 
 private: