From 2db1211c9a24a0cd22da1d3ddcddf564f814fc0a Mon Sep 17 00:00:00 2001
From: David Gow <david@ingeniumdigital.com>
Date: Tue, 8 Jul 2014 00:01:55 +0800
Subject: [PATCH] Quadtrees! (Almost)

---
 src/document.cpp |  6 ++++++
 src/document.h   |  2 +-
 src/main.cpp     |  1 +
 src/quadtree.h   |  1 +
 src/view.cpp     | 26 ++++++++++++++++++++++----
 src/view.h       |  3 +++
 6 files changed, 34 insertions(+), 5 deletions(-)

diff --git a/src/document.cpp b/src/document.cpp
index e49e52e..76a5349 100644
--- a/src/document.cpp
+++ b/src/document.cpp
@@ -142,6 +142,12 @@ void Document::Load(const string & filename)
 		}
 	}
 	Debug("Successfully loaded %u objects from \"%s\"", ObjectCount(), filename.c_str());
+#ifndef QUADTREE_DISABLED
+	if (m_quadtree.root_id == QUADTREE_EMPTY)
+	{
+		GenBaseQuadtree();
+	}
+#endif
 }
 
 void Document::Add(ObjectType type, const Rect & bounds, unsigned data_index)
diff --git a/src/document.h b/src/document.h
index b02c798..0f2fea1 100644
--- a/src/document.h
+++ b/src/document.h
@@ -26,7 +26,7 @@ namespace IPDF
 			unsigned AddBezierData(const Bezier & bezier);
 
 #ifndef QUADTREE_DISABLED
-			inline const QuadTree& GetQuadTree() const { return m_quadtree; }
+			inline const QuadTree& GetQuadTree() { if (m_quadtree.root_id == QUADTREE_EMPTY) { GenBaseQuadtree(); } return m_quadtree; }
 #endif
 
 		private:
diff --git a/src/main.cpp b/src/main.cpp
index 91e362c..2cfb73b 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -98,6 +98,7 @@ int main(int argc, char ** argv)
 			}
 		}
 		doc.Add(BEZIER, Rect(0.1,0.1,0.8,0.8), 0);
+		doc.Add(CIRCLE_FILLED, Rect(0.1,0.1,0.8,0.8), 0);
 	}
 	Debug("Start!");
 	Rect bounds(b[0],b[1],b[2],b[3]);
diff --git a/src/quadtree.h b/src/quadtree.h
index 671ee0f..d5eddd8 100644
--- a/src/quadtree.h
+++ b/src/quadtree.h
@@ -42,6 +42,7 @@ namespace IPDF
 
 	struct QuadTree
 	{
+		QuadTree() : root_id(QUADTREE_EMPTY) {}
 		QuadTreeIndex root_id;
 		std::vector<QuadTreeNode> nodes;
 	};
diff --git a/src/view.cpp b/src/view.cpp
index 73331ef..02859c5 100644
--- a/src/view.cpp
+++ b/src/view.cpp
@@ -124,6 +124,28 @@ Rect View::TransformToViewCoords(const Rect& inp) const
  * @param height - Height of View to render
  */
 void View::Render(int width, int height)
+{
+#ifdef QUADTREE_DISABLED
+	RenderRange(width, height, 0, m_document.ObjectCount());
+#else
+	RenderQuadtreeNode(width, height, m_current_quadtree_node, m_quadtree_max_depth);
+#endif
+}
+
+#ifndef QUADTREE_DISABLED
+void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int remaining_depth)
+{
+	if (node == QUADTREE_EMPTY) return;
+	if (!remaining_depth) return;
+	RenderRange(width, height, m_document.GetQuadTree().nodes[node].object_begin, m_document.GetQuadTree().nodes[node].object_end);
+	RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].top_left, remaining_depth-1);
+	RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].top_right, remaining_depth-1);
+	RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].bottom_left, remaining_depth-1);
+	RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].bottom_right, remaining_depth-1);
+}
+#endif
+
+void View::RenderRange(int width, int height, unsigned first_obj, unsigned last_obj)
 {
 	// View dimensions have changed (ie: Window was resized)
 	int prev_width = m_cached_display.GetWidth();
@@ -168,10 +190,6 @@ void View::Render(int width, int height)
 	m_cached_display.Bind(); //NOTE: This is redundant; Clear already calls Bind
 	m_cached_display.Clear();
 
-	// When we QuadTree, this will be magic.
-	int first_obj = 0;
-	int last_obj = m_document.ObjectCount();
-
 	// Render using GPU
 	if (m_use_gpu_rendering) 
 	{
diff --git a/src/view.h b/src/view.h
index ca4c808..5e30ef7 100644
--- a/src/view.h
+++ b/src/view.h
@@ -53,6 +53,8 @@ namespace IPDF
 			void PrepareRender(); // call when m_render_dirty is true
 			void UpdateObjBoundsVBO(); // call when m_buffer_dirty is true
 
+			void RenderRange(int width, int height, unsigned first_obj, unsigned last_obj);
+
 			bool m_use_gpu_transform;
 			bool m_use_gpu_rendering;
 			bool m_bounds_dirty; // the view bounds has changed (occurs when changing view)
@@ -77,6 +79,7 @@ namespace IPDF
 #ifndef QUADTREE_DISABLED
 			QuadTreeIndex m_current_quadtree_node;	// The highest node we will traverse.
 			int m_quadtree_max_depth;		// The maximum quadtree depth.
+			void RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int remaining_depth);
 
 #endif
 	};
-- 
2.20.1