Critics are panning the quadtree's panning.
authorDavid Gow <david@ingeniumdigital.com>
Mon, 29 Sep 2014 04:20:55 +0000 (12:20 +0800)
committerDavid Gow <david@ingeniumdigital.com>
Mon, 29 Sep 2014 04:20:55 +0000 (12:20 +0800)
(It's broken)

src/bezier.cpp
src/bezier.h
src/document.cpp
src/quadtree.cpp
src/quadtree.h
src/view.cpp
src/view.h

index 67b384c..9b594a0 100644 (file)
@@ -58,7 +58,7 @@ static void CubicSolveSegment(vector<Real> & roots, const Real & a, const Real &
                //return;
        
        bool negative = (u < l); // lower point > 0, upper point < 0
-       Debug("%ft^3 + %ft^2 + %ft + %f is negative (%f < %f) %d", a,b,c,d,u,l, negative);
+       //Debug("%ft^3 + %ft^2 + %ft + %f is negative (%f < %f) %d", a,b,c,d,u,l, negative);
        while (tu - tl > delta)
        {
                Real t(tu+tl);
@@ -89,7 +89,7 @@ vector<Real> SolveCubic(const Real & a, const Real & b, const Real & c, const Re
        Real tu(max);
        Real tl(min);
        vector<Real> turns(SolveQuadratic(a*3, b*2, c));
-       Debug("%u turning points", turns.size());
+       //Debug("%u turning points", turns.size());
        for (unsigned i = 1; i < turns.size(); ++i)
        {
                tu = turns[i];
index 01da922..25b4796 100644 (file)
@@ -235,16 +235,16 @@ namespace IPDF
 
                Bezier ReParametrise(const Real& t0, const Real& t1)
                {
-                       Debug("Reparametrise: %f -> %f",Double(t0),Double(t1));
+                       //Debug("Reparametrise: %f -> %f",Double(t0),Double(t1));
                        Bezier new_bezier;
                        // Subdivide to get from [0,t1]
                        new_bezier = DeCasteljauSubdivideLeft(t1);
                        // Convert t0 from [0,1] range to [0, t1]
                        Real new_t0 = t0 / t1;
-                       Debug("New t0 = %f", Double(new_t0));
+                       //Debug("New t0 = %f", Double(new_t0));
                        new_bezier = new_bezier.DeCasteljauSubdivideRight(new_t0);
 
-                       Debug("%s becomes %s", this->Str().c_str(), new_bezier.Str().c_str());
+                       //Debug("%s becomes %s", this->Str().c_str(), new_bezier.Str().c_str());
                        return new_bezier;
                }
                
@@ -256,21 +256,21 @@ namespace IPDF
 
                        // Find its roots.
                        std::vector<Real> x_intersection = SolveXParam(r.x);
-                       Debug("Found %d intersections on left edge", x_intersection.size());
+                       //Debug("Found %d intersections on left edge", x_intersection.size());
 
                        // And for the other side.
 
                        std::vector<Real> x_intersection_pt2 = SolveXParam(r.x + r.w);
                        x_intersection.insert(x_intersection.end(), x_intersection_pt2.begin(), x_intersection_pt2.end());
-                       Debug("Found %d intersections on right edge (total x: %d)", x_intersection_pt2.size(), x_intersection.size());
+                       //Debug("Found %d intersections on right edge (total x: %d)", x_intersection_pt2.size(), x_intersection.size());
 
                        // Find its roots.
                        std::vector<Real> y_intersection = SolveYParam(r.y);
-                       Debug("Found %d intersections on top edge", y_intersection.size());
+                       //Debug("Found %d intersections on top edge", y_intersection.size());
 
                        std::vector<Real> y_intersection_pt2 = SolveYParam(r.y+r.h);
                        y_intersection.insert(y_intersection.end(), y_intersection_pt2.begin(), y_intersection_pt2.end());
-                       Debug("Found %d intersections on bottom edge (total y: %d)", y_intersection_pt2.size(), y_intersection.size());
+                       //Debug("Found %d intersections on bottom edge (total y: %d)", y_intersection_pt2.size(), y_intersection.size());
 
                        // Merge and sort.
                        x_intersection.insert(x_intersection.end(), y_intersection.begin(), y_intersection.end());
@@ -278,13 +278,13 @@ namespace IPDF
                        x_intersection.push_back(Real(1));
                        std::sort(x_intersection.begin(), x_intersection.end());
 
-                       Debug("Found %d intersections.\n", x_intersection.size());
-                       for(auto t : x_intersection)
+                       //Debug("Found %d intersections.\n", x_intersection.size());
+                       /*for(auto t : x_intersection)
                        {
                                Real ptx, pty;
                                Evaluate(ptx, pty, t);
                                Debug("Root: t = %f, (%f,%f)", Double(t), Double(ptx), Double(pty));
-                       }
+                       }*/
                        
                        std::vector<Bezier> all_beziers;
                        if (x_intersection.size() <= 2)
@@ -297,17 +297,17 @@ namespace IPDF
                        {
                                Real t1 = *it;
                                if (t1 == t0) continue;
-                               Debug(" -- t0: %f to t1: %f: %f", Double(t0), Double(t1), Double((t1 + t0)/Real(2)));
+                               //Debug(" -- t0: %f to t1: %f: %f", Double(t0), Double(t1), Double((t1 + t0)/Real(2)));
                                Real ptx, pty;
                                Evaluate(ptx, pty, ((t1 + t0) / Real(2)));
                                if (r.PointIn(ptx, pty))
                                {
-                                       Debug("Adding segment: (point at %f, %f)", Double(ptx), Double(pty));
+                                       //Debug("Adding segment: (point at %f, %f)", Double(ptx), Double(pty));
                                        all_beziers.push_back(this->ReParametrise(t0, t1));
                                }
                                else
                                {
-                                       Debug("Segment removed (point at %f, %f)", Double(ptx), Double(pty));
+                                       //Debug("Segment removed (point at %f, %f)", Double(ptx), Double(pty));
                                }
                                t0 = t1;
                        }
index 71f4205..32df613 100644 (file)
@@ -168,7 +168,7 @@ int Document::ClipObjectToQuadChild(int object_id, QuadTreeNodeChildren type)
 QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren type)
 {
        QuadTreeIndex new_index = m_quadtree.nodes.size();
-       Debug("-------------- Generating Quadtree Node %d (parent %d) ----------------------", new_index, parent);
+       Debug("-------------- Generating Quadtree Node %d (parent %d, type %d) ----------------------", new_index, parent, type);
        m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, parent, type, 0, 0, -1});
 
        m_quadtree.nodes[new_index].object_begin = m_objects.bounds.size();
index 8474a7f..3d5dbee 100644 (file)
@@ -1,5 +1,6 @@
 #ifndef QUADTREE_REMOVED
 #include "quadtree.h"
+#include "document.h"
 
 namespace IPDF {
 
@@ -47,7 +48,7 @@ bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        if (src.y + src.h < dst.y) return false;
        if (src.x > dst.x + dst.w) return false;
        if (src.y > dst.y + dst.h) return false;
-       Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
+       //Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
        return true;
 }
 
@@ -59,13 +60,13 @@ bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        if (src.y < dst.y) return false;
        if (src.x + src.w > dst.x + dst.w) return false;
        if (src.y + src.h > dst.y + dst.h) return false;
-       Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
+       //Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
        return true;
 }
 
 
 
-QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const
+QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *addTo) const
 {
        if (!xdir && !ydir) return start;
 
@@ -79,22 +80,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
                case QTC_BOTTOM_LEFT:
                {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
+                       {
                                newNode = nodes[nodes[start].parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[nodes[start].parent].bottom_right;
-                               
-                       return GetNeighbour(newNode, xdir - 1, ydir);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir - 1, ydir, addTo);
                }
                case QTC_TOP_RIGHT:
                case QTC_BOTTOM_RIGHT:
                {
-                       QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
+                       QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
                        if (right_parent == -1) return -1;
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
+                       {
                                newNode = nodes[right_parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[right_parent].bottom_left;
-                       return GetNeighbour(newNode, xdir - 1, ydir);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir - 1, ydir, addTo);
                }
                default:
                        return -1;
@@ -111,22 +135,46 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
                case QTC_BOTTOM_RIGHT:
                {
                        if (nodes[start].child_type == QTC_TOP_RIGHT)
+                       {
                                newNode = nodes[nodes[start].parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[nodes[start].parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                                
-                       return GetNeighbour(newNode, xdir + 1, ydir);
+                       return GetNeighbour(newNode, xdir + 1, ydir, addTo);
                }
                case QTC_TOP_LEFT:
                case QTC_BOTTOM_LEFT:
                {
-                       QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
+                       QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
                        if (left_parent == -1) return -1;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
+                       {
                                newNode = nodes[left_parent].top_right;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[left_parent].bottom_right;
-                       return GetNeighbour(newNode, xdir + 1, ydir);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir + 1, ydir, addTo);
                }
                default:
                        return -1;
@@ -142,22 +190,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
                case QTC_TOP_RIGHT:
                {
                        if (nodes[start].child_type == QTC_TOP_LEFT)
+                       {
                                newNode = nodes[nodes[start].parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[nodes[start].parent].bottom_right;
-                               
-                       return GetNeighbour(newNode, xdir, ydir - 1);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir, ydir - 1, addTo);
                }
                case QTC_BOTTOM_LEFT:
                case QTC_BOTTOM_RIGHT:
                {
-                       QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
+                       QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
                        if (bottom_parent == -1) return -1;
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+                       {
                                newNode = nodes[bottom_parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[bottom_parent].top_right;
-                       return GetNeighbour(newNode, xdir, ydir - 1);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir, ydir - 1, addTo);
                }
                default:
                        return -1;
@@ -173,22 +244,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
                case QTC_BOTTOM_RIGHT:
                {
                        if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+                       {
                                newNode = nodes[nodes[start].parent].top_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[nodes[start].parent].top_right;
-                               
-                       return GetNeighbour(newNode, xdir, ydir + 1);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+                               }
+                       }       
+                       return GetNeighbour(newNode, xdir, ydir + 1, addTo);
                }
                case QTC_TOP_LEFT:
                case QTC_TOP_RIGHT:
                {
-                       QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
+                       QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
                        if (top_parent == -1) return -1;
                        if (nodes[start].child_type == QTC_TOP_LEFT)
+                       {
                                newNode = nodes[top_parent].bottom_left;
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
+                               }
+                       }
                        else
+                       {
                                newNode = nodes[top_parent].bottom_right;
-                       return GetNeighbour(newNode, xdir, ydir + 1);
+                               if (addTo && newNode == -1)
+                               {
+                                       newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
+                               }
+                       }
+                       return GetNeighbour(newNode, xdir, ydir + 1, addTo);
                }
                default:
                        return -1;
index 1c1c025..e35da2e 100644 (file)
@@ -13,6 +13,7 @@ namespace IPDF
 
        typedef int QuadTreeIndex;
        static const QuadTreeIndex QUADTREE_EMPTY = -1;
+       class Document;
 
        enum QuadTreeNodeChildren
        {
@@ -49,7 +50,7 @@ namespace IPDF
                QuadTreeIndex root_id;
                std::vector<QuadTreeNode> nodes;
 
-               QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const;
+               QuadTreeIndex GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *doc) const;
 
        };
 
index 8063cec..e5f81bb 100644 (file)
@@ -201,7 +201,7 @@ void View::Render(int width, int height)
 #ifndef QUADTREE_DISABLED
        if (m_bounds_dirty || !m_lazy_rendering)
        {
-               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 ( 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)
@@ -210,6 +210,32 @@ void View::Render(int width, int height)
                                m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].parent;
                        }
                }
+
+               // TODO: Support generating new parent nodes.
+               if (false && m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY)
+               {
+                       if (m_bounds.x < -0.5)
+                       {
+                               m_bounds = Rect(m_bounds.x + 1, m_bounds.y, m_bounds.w, m_bounds.h);
+                               m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, -1, 0, &m_document);
+                       }
+                       if (m_bounds.y < -0.5)
+                       {
+                               m_bounds = Rect(m_bounds.x, m_bounds.y + 1, m_bounds.w, m_bounds.h);
+                               m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, -1, &m_document);
+                       }
+                       if (m_bounds.w + m_bounds.x > 0.5)
+                       {
+                               m_bounds = Rect(m_bounds.x - 1, m_bounds.y, m_bounds.w, m_bounds.h);
+                               m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 1, 0, &m_document);
+                       }
+                       if (m_bounds.h + m_bounds.y > 0.5)
+                       {
+                               m_bounds = Rect(m_bounds.x, m_bounds.y - 1, m_bounds.w, m_bounds.h);
+                               m_current_quadtree_node = m_document.GetQuadTree().GetNeighbour(m_current_quadtree_node, 0, 1, &m_document);
+                       }
+               }
+
                if (ContainedInQuadChild(m_bounds, QTC_TOP_LEFT))
                {
                        if (m_document.GetQuadTree().nodes[m_current_quadtree_node].top_left == QUADTREE_EMPTY)
@@ -332,49 +358,56 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem
        {
                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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, -1, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 0, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, -1, 1, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, -1, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 0, 1, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, -1, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 0, &m_document), remaining_depth - 1);
        }
+       m_bounds = old_bounds;
        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);
+               RenderQuadtreeNode(width, height, m_document.GetQuadTree().GetNeighbour(node, 1, 1, &m_document), remaining_depth - 1);
        }
        m_bounds = old_bounds;
        m_bounds_dirty = true;
index 6be1ebf..e93d673 100644 (file)
@@ -10,7 +10,7 @@
 #define USE_GPU_RENDERING true
 #define USE_SHADING !(USE_GPU_RENDERING) && true
 
-#define TRANSFORM_OBJECTS_NOT_VIEW
+//#define TRANSFORM_OBJECTS_NOT_VIEW
 
 namespace IPDF
 {

UCC git Repository :: git.ucc.asn.au