From: David Gow <david@ingeniumdigital.com>
Date: Sun, 6 Jul 2014 08:30:39 +0000 (+0800)
Subject: Some initial QuadTree goodness.
X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=commitdiff_plain;h=35e4687acd16a28fc923a75d254cdb4fd2fbc524

Some initial QuadTree goodness.
---

diff --git a/src/document.cpp b/src/document.cpp
index 921763a..e49e52e 100644
--- a/src/document.cpp
+++ b/src/document.cpp
@@ -85,6 +85,16 @@ void Document::Save(const string & filename)
 	Debug("Successfully saved %u objects to \"%s\"", ObjectCount(), filename.c_str());
 }
 
+#ifndef QUADTREE_DISABLED
+
+void Document::GenBaseQuadtree()
+{
+	m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QTC_UNKNOWN, 0, ObjectCount()});
+	m_quadtree.root_id = 0;
+}
+
+#endif
+
 void Document::Load(const string & filename)
 {
 	m_objects.bounds.clear();
diff --git a/src/document.h b/src/document.h
index 5ec5dad..b02c798 100644
--- a/src/document.h
+++ b/src/document.h
@@ -2,6 +2,7 @@
 #define _DOCUMENT_H
 
 #include "ipdf.h"
+#include "quadtree.h"
 
 namespace IPDF
 {
@@ -24,9 +25,17 @@ namespace IPDF
 			void Add(ObjectType type, const Rect & bounds, unsigned data_index = 0);
 			unsigned AddBezierData(const Bezier & bezier);
 
+#ifndef QUADTREE_DISABLED
+			inline const QuadTree& GetQuadTree() const { return m_quadtree; }
+#endif
+
 		private:
 			friend class View;
 			Objects m_objects;
+#ifndef QUADTREE_DISABLED
+			QuadTree m_quadtree;
+			void GenBaseQuadtree();
+#endif
 			unsigned m_count;
 			
 
diff --git a/src/quadtree.h b/src/quadtree.h
new file mode 100644
index 0000000..671ee0f
--- /dev/null
+++ b/src/quadtree.h
@@ -0,0 +1,54 @@
+#ifndef _QUADTREE_H
+#define _QUADTREE_H
+
+
+#ifndef QUADTREE_REMOVED
+
+
+#include "common.h"
+
+namespace IPDF
+{
+
+	typedef int QuadTreeIndex;
+	static const QuadTreeIndex QUADTREE_EMPTY = -1;
+
+	enum QuadTreeNodeChildren
+	{
+		QTC_UNKNOWN,
+		QTC_TOP_LEFT,
+		QTC_TOP_RIGHT,
+		QTC_BOTTOM_LEFT,
+		QTC_BOTTOM_RIGHT
+	};
+
+	// Represents a single node in a quadtree.
+	struct QuadTreeNode
+	{
+		// Indices of children nodes, QUADTREE_EMPTY if no such child.
+		QuadTreeIndex top_left;
+		QuadTreeIndex top_right;
+		QuadTreeIndex bottom_left;
+		QuadTreeIndex bottom_right;
+		// Parent node id. QUADTREE_EMPTY if root.
+		QuadTreeIndex parent;
+		// Which child am I?
+		QuadTreeNodeChildren child_type;
+		// First object in the node.
+		unsigned object_begin;
+		// Last object in the node.
+		unsigned object_end;
+	};
+
+	struct QuadTree
+	{
+		QuadTreeIndex root_id;
+		std::vector<QuadTreeNode> nodes;
+	};
+}
+
+#else
+#define QUADTREE_DISABLED
+#endif
+
+#endif
diff --git a/src/view.cpp b/src/view.cpp
index eb269a2..73331ef 100644
--- a/src/view.cpp
+++ b/src/view.cpp
@@ -32,6 +32,12 @@ View::View(Document & document, Screen & screen, const Rect & bounds, const Colo
 	// 2. Implement class inheriting from ObjectRenderer using that type in objectrenderer.h and objectrenderer.cpp
 	// 3. Add it here
 	// 4. Profit
+
+
+#ifndef QUADTREE_DISABLED
+	m_quadtree_max_depth = 1;
+	m_current_quadtree_node = document.GetQuadTree().root_id;
+#endif
 }
 
 /**
diff --git a/src/view.h b/src/view.h
index ff91f46..ca4c808 100644
--- a/src/view.h
+++ b/src/view.h
@@ -73,6 +73,12 @@ namespace IPDF
 			// Trust me it will be easier to generalise things this way. Even though there are pointers.
 			std::vector<ObjectRenderer*> m_object_renderers; 
 			uint8_t * m_cpu_rendering_pixels; // pixels to be used for CPU rendering
+
+#ifndef QUADTREE_DISABLED
+			QuadTreeIndex m_current_quadtree_node;	// The highest node we will traverse.
+			int m_quadtree_max_depth;		// The maximum quadtree depth.
+
+#endif
 	};
 }