Heinous Quadtree crimes.

"The bézier tiptoed out of bed. What an adventure it would be to go beyond the
quadtree node in which it had lived its entire life. Its mother had told it
sternly that it was dangerous to wander the dark  wastes beyond the root node.
Bobby Bézier had never believed the stories, though: there were no such things
as wild NaNs that ate all of the coefficients of naughty boys. Bobby looked up
at the sky: the infinite void of night penetrated only by the debug text high
above. Tentatively, he inched one of his endpoints over the quadtree node
boundary. But alas: his mother had perhaps been right all along. She would scald
him so... how would he hide the fact that his endpoint had been clipped right
off!"

diff --git a/src/quadtree.cpp b/src/quadtree.cpp
index b0c0eb5..8474a7f 100644 (file)
--- a/src/quadtree.cpp
+++ b/src/quadtree.cpp
@@ -65,10 +65,11 @@ bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 
 
 
-QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
+QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const
 {
        if (!xdir && !ydir) return start;
 
+       QuadTreeIndex newNode;
        // Try moving to the right if that's easy.
        if (xdir > 0)
        {
@@ -76,23 +77,27 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_LEFT:
                case QTC_BOTTOM_LEFT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[nodes[start].parent].top_right;
+                               newNode = nodes[nodes[start].parent].top_right;
                        else
-                               newNode = node[nodes[start].parent].bottom_right;
+                               newNode = nodes[nodes[start].parent].bottom_right;
                                
                        return GetNeighbour(newNode, xdir - 1, ydir);
+               }
                case QTC_TOP_RIGHT:
                case QTC_BOTTOM_RIGHT:
+               {
                        QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
                        if (right_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
-                               newNode = node[right_parent].top_left;
+                               newNode = nodes[right_parent].top_left;
                        else
-                               newNode = node[right_parent].bottom_left;
+                               newNode = nodes[right_parent].bottom_left;
                        return GetNeighbour(newNode, xdir - 1, ydir);
+               }
+               default:
+                       return -1;
 
                }
        }
@@ -104,24 +109,27 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_RIGHT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
-                               newNode = node[nodes[start].parent].top_left;
+                               newNode = nodes[nodes[start].parent].top_left;
                        else
-                               newNode = node[nodes[start].parent].bottom_left;
+                               newNode = nodes[nodes[start].parent].bottom_left;
                                
                        return GetNeighbour(newNode, xdir + 1, ydir);
+               }
                case QTC_TOP_LEFT:
                case QTC_BOTTOM_LEFT:
+               {
                        QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
                        if (left_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[left_parent].top_right;
+                               newNode = nodes[left_parent].top_right;
                        else
-                               newNode = node[left_parent].bottom_right;
+                               newNode = nodes[left_parent].bottom_right;
                        return GetNeighbour(newNode, xdir + 1, ydir);
-
+               }
+               default:
+                       return -1;
                }
        }
        
@@ -132,24 +140,27 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_TOP_LEFT:
                case QTC_TOP_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[nodes[start].parent].bottom_left;
+                               newNode = nodes[nodes[start].parent].bottom_left;
                        else
-                               newNode = node[nodes[start].parent].bottom_right;
+                               newNode = nodes[nodes[start].parent].bottom_right;
                                
                        return GetNeighbour(newNode, xdir, ydir - 1);
+               }
                case QTC_BOTTOM_LEFT:
                case QTC_BOTTOM_RIGHT:
+               {
                        QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
                        if (bottom_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
-                               newNode = node[bottom__parent].top_left;
+                               newNode = nodes[bottom_parent].top_left;
                        else
-                               newNode = node[bottom_parent].top_right;
+                               newNode = nodes[bottom_parent].top_right;
                        return GetNeighbour(newNode, xdir, ydir - 1);
-
+               }
+               default:
+                       return -1;
                }
        }
 
@@ -160,24 +171,27 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir)
                {
                case QTC_BOTTOM_LEFT:
                case QTC_BOTTOM_RIGHT:
-                       QuadTreeIndex newNode;
+               {
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
-                               newNode = node[nodes[start].parent].top_left;
+                               newNode = nodes[nodes[start].parent].top_left;
                        else
-                               newNode = node[nodes[start].parent].top_right;
+                               newNode = nodes[nodes[start].parent].top_right;
                                
                        return GetNeighbour(newNode, xdir, ydir + 1);
+               }
                case QTC_TOP_LEFT:
-               case QTC_BOTTOM_LEFT:
+               case QTC_TOP_RIGHT:
+               {
                        QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
                        if (top_parent == -1) return -1;
-                       QuadTreeIndex newNode;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
-                               newNode = node[top_parent].bottom_left;
+                               newNode = nodes[top_parent].bottom_left;
                        else
-                               newNode = node[top_parent].bottom_right;
+                               newNode = nodes[top_parent].bottom_right;
                        return GetNeighbour(newNode, xdir, ydir + 1);
-
+               }
+               default:
+                       return -1;
                }
        }
        return -1;

diff --git a/src/quadtree.h b/src/quadtree.h
index ac02146..4b75269 100644 (file)
--- a/src/quadtree.h
+++ b/src/quadtree.h
@@ -47,7 +47,7 @@ namespace IPDF
                QuadTreeIndex root_id;
                std::vector<QuadTreeNode> nodes;
 
-               QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir);
+               QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const;
 
        };
 

diff --git a/src/rect.h b/src/rect.h
index 3c4a105..7a0f1e1 100644 (file)
--- a/src/rect.h
+++ b/src/rect.h
@@ -26,6 +26,15 @@ namespace IPDF
                        if (pt_y >= y + h) return false;
                        return true;
                }
+
+               inline bool Intersects(const Rect& other) const
+               {
+                       if (x + w < other.x) return false;
+                       if (y + h < other.y) return false;
+                       if (x > other.x + other.w) return false;
+                       if (y > other.y + other.h) return false;
+                       return true;
+               }
        };
 
        inline Rect TransformRectCoordinates(const Rect& view, const Rect& r)

diff --git a/src/view.cpp b/src/view.cpp
index 554fb03..52a4c6d 100644 (file)
--- a/src/view.cpp
+++ b/src/view.cpp
@@ -44,7 +44,7 @@ View::View(Document & document, Screen & screen, const Rect & bounds, const Colo
 
 
 #ifndef QUADTREE_DISABLED
-       m_quadtree_max_depth = 1;
+       m_quadtree_max_depth = 2;
        m_current_quadtree_node = document.GetQuadTree().root_id;
 #endif
 }
@@ -173,7 +173,7 @@ void View::Render(int width, int height)
 #ifndef QUADTREE_DISABLED
        if (m_bounds_dirty)
        {
-               if ( (m_bounds.x > 1.0 || m_bounds.x < 0.0 || m_bounds.y > 1.0 || m_bounds.y < 0.0 || m_bounds.w > 1.0 || m_bounds.h > 1.0))
+               if ( false &&  (m_bounds.x > 1.0 || m_bounds.x < 0.0 || m_bounds.y > 1.0 || m_bounds.y < 0.0 || m_bounds.w > 1.0 || m_bounds.h > 1.0))
                {
                        //TODO: Generate a new parent node.
                        if (m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY)
@@ -287,6 +287,58 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem
        m_bounds_dirty = true;
        RenderRange(width, height, m_document.GetQuadTree().nodes[node].object_begin, m_document.GetQuadTree().nodes[node].object_end);
 
+       if (m_bounds.Intersects(Rect(-1,-1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x - 1, m_bounds.y - 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, -1), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(-1,0,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x - 1, m_bounds.y, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 0), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(-1,1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x - 1, m_bounds.y + 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 1), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(0,-1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x, m_bounds.y - 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, -1), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(0,1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x, m_bounds.y + 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, 1), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(1,-1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x + 1, m_bounds.y - 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, -1), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(1,0,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x + 1, m_bounds.y, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 0), remaining_depth - 1);
+       }
+       if (m_bounds.Intersects(Rect(1,1,1,1)))
+       {
+               m_bounds = Rect(m_bounds.x + 1, m_bounds.y + 1, m_bounds.w, m_bounds.h);
+               m_bounds_dirty = true;
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 1), remaining_depth - 1);
+       }
+       m_bounds = old_bounds;
+       m_bounds_dirty = true;
+
+#if 0
        m_bounds = TransformToQuadChild(old_bounds, QTC_TOP_LEFT);
        m_bounds_dirty = true;
        RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].top_left, remaining_depth-1);
@@ -301,6 +353,7 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem
        RenderQuadtreeNode(width, height, m_document.GetQuadTree().nodes[node].bottom_right, remaining_depth-1);
        m_bounds = old_bounds;
        m_bounds_dirty = true;
+#endif
 }
 #endif