Some quadtree stuff: bugfix + mutation

diff --git a/src/bezier.cpp b/src/bezier.cpp
index 99611dc..67b384c 100644 (file)
--- a/src/bezier.cpp
+++ b/src/bezier.cpp
@@ -54,9 +54,11 @@ static void CubicSolveSegment(vector<Real> & roots, const Real & a, const Real &
        Real l = a*tl*tl*tl + b*tl*tl + c*tl + d;
        Real u = a*tu*tu*tu + b*tu*tu + c*tu + d;
        if ((l < 0 && u < 0) || (l > 0 && u > 0))
-               return;
+               Debug("Discarding segment (no roots) l = %f (%f), u = %f (%f)", tl, l, tu, u);
+               //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);
        while (tu - tl > delta)
        {
                Real t(tu+tl);
@@ -87,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];

diff --git a/src/bezier.h b/src/bezier.h
index 206cbc8..d9aa177 100644 (file)
--- a/src/bezier.h
+++ b/src/bezier.h
@@ -15,7 +15,7 @@ namespace IPDF
        
        extern std::vector<Real> SolveQuadratic(const Real & a, const Real & b, const Real & c, const Real & min = 0, const Real & max = 1);
 
-       extern std::vector<Real> SolveCubic(const Real & a, const Real & b, const Real & c, const Real & d, const Real & min = 0, const Real & max = 1, const Real & delta = 1e-4);
+       extern std::vector<Real> SolveCubic(const Real & a, const Real & b, const Real & c, const Real & d, const Real & min = 0, const Real & max = 1, const Real & delta = 1e-9);
 
        /** A _cubic_ bezier. **/
        struct Bezier
@@ -256,17 +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());
 
                        // 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());
 
                        // Find its roots.
                        std::vector<Real> y_intersection = SolveYParam(r.y);
+                       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());
 
                        // Merge and sort.
                        x_intersection.insert(x_intersection.end(), y_intersection.begin(), y_intersection.end());

diff --git a/src/document.cpp b/src/document.cpp
index 5890730..b6bf955 100644 (file)
--- a/src/document.cpp
+++ b/src/document.cpp
@@ -94,9 +94,8 @@ void Document::Save(const string & filename)
 
 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.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QTC_UNKNOWN, 0, ObjectCount(), -1});
        m_quadtree.root_id = 0;
-       GenQuadChild(0, QTC_TOP_LEFT);
 }
 
 int Document::ClipObjectToQuadChild(int object_id, QuadTreeNodeChildren type)
@@ -169,7 +168,8 @@ int Document::ClipObjectToQuadChild(int object_id, QuadTreeNodeChildren type)
 QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren type)
 {
        QuadTreeIndex new_index = m_quadtree.nodes.size();
-       m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, parent, type, 0, 0});
+       Debug("-------------- Generating Quadtree Node %d (parent %d) ----------------------", new_index, parent);
+       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();
        for (unsigned i = m_quadtree.nodes[parent].object_begin; i < m_quadtree.nodes[parent].object_end; ++i)
@@ -204,7 +204,7 @@ QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren
 QuadTreeIndex Document::GenQuadParent(QuadTreeIndex child, QuadTreeNodeChildren type)
 {
        QuadTreeIndex new_index = m_quadtree.nodes.size();
-       m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, -1, QTC_UNKNOWN, 0, 0});
+       m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, -1, QTC_UNKNOWN, 0, 0, -1});
 
        m_quadtree.nodes[new_index].object_begin = m_objects.bounds.size();
        for (unsigned i = m_quadtree.nodes[child].object_begin; i < m_quadtree.nodes[child].object_end; ++i)
@@ -324,11 +324,28 @@ unsigned Document::AddBezier(const Bezier & bezier)
        return Add(BEZIER, bounds, index);
 }
 
-unsigned Document::Add(ObjectType type, const Rect & bounds, unsigned data_index)
+unsigned Document::Add(ObjectType type, const Rect & bounds, unsigned data_index, QuadTreeIndex qti)
 {
        m_objects.types.push_back(type);
        m_objects.bounds.push_back(bounds);
        m_objects.data_indices.push_back(data_index);
+#ifndef QUADTREE_DISABLED
+       if (qti != -1)
+       {
+               if (m_count == m_quadtree.nodes[qti].object_end+1)
+               {
+                       m_quadtree.nodes[qti].object_end++;
+               }
+               else
+               {
+                       QuadTreeIndex overlay = m_quadtree.nodes.size();
+                       m_quadtree.nodes.push_back(m_quadtree.nodes[qti]);
+                       m_quadtree.nodes[overlay].object_begin = m_count;
+                       m_quadtree.nodes[overlay].object_end = m_count+1;
+                       m_quadtree.nodes[qti].next_overlay = overlay;
+               }
+       }
+#endif
        return (m_count++); // Why can't we just use the size of types or something?
 }
 

diff --git a/src/document.h b/src/document.h
index eb8710e..28caf3d 100644 (file)
--- a/src/document.h
+++ b/src/document.h
@@ -54,7 +54,7 @@ namespace IPDF
 
                        unsigned AddPath(unsigned start_index, unsigned end_index, const Colour & shading=Colour(0.6,0.6,0.6,1), const Colour & stroke=Colour(0,0,0,0));
                        unsigned AddBezier(const Bezier & bezier);
-                       unsigned Add(ObjectType type, const Rect & bounds, unsigned data_index = 0);
+                       unsigned Add(ObjectType type, const Rect & bounds, unsigned data_index = 0, QuadTreeIndex qtnode = 0);
                        unsigned AddBezierData(const Bezier & bezier);
                        unsigned AddPathData(const Path & path);
 

diff --git a/src/quadtree.h b/src/quadtree.h
index 4b75269..1c1c025 100644 (file)
--- a/src/quadtree.h
+++ b/src/quadtree.h
@@ -39,6 +39,8 @@ namespace IPDF
                unsigned object_begin;
                // Last object in the node.
                unsigned object_end;
+               // Linked list of "extra" nodes
+               QuadTreeIndex next_overlay;
        };
 
        struct QuadTree

diff --git a/src/svg-tests/cubicbeziers.svg b/src/svg-tests/cubicbeziers.svg
index 9597357..8bcd942 100644 (file)
--- a/src/svg-tests/cubicbeziers.svg
+++ b/src/svg-tests/cubicbeziers.svg
@@ -62,7 +62,7 @@
        id="path2985"
        inkscape:connector-curvature="0"
        sodipodi:nodetypes="cc" />
-    <path
+    <!--<path
        style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
        d="m 380.35613,179.82644 c -137.24439,-190.777369 508.57143,-69.28571 70,2.14286"
        id="path2985-1"
@@ -103,6 +103,6 @@
        d="M 367.54579,602.1648 C 175.33857,815.57053 683.74439,370.27416 508.25647,614.40918"
        id="path2985-1-6-2-5-5-5-6"
        inkscape:connector-curvature="0"
-       sodipodi:nodetypes="cc" />
+       sodipodi:nodetypes="cc" />-->
   </g>
 </svg>

diff --git a/src/view.cpp b/src/view.cpp
index 52a4c6d..2b21225 100644 (file)
--- a/src/view.cpp
+++ b/src/view.cpp
@@ -173,7 +173,7 @@ void View::Render(int width, int height)
 #ifndef QUADTREE_DISABLED
        if (m_bounds_dirty)
        {
-               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))
+               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))
                {
                        //TODO: Generate a new parent node.
                        if (m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY)
@@ -227,8 +227,16 @@ void View::Render(int width, int height)
                        m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right;
                }
        }
-       m_screen.DebugFontPrintF("Current View QuadTree Node: %d (objs: %d -> %d)\n", m_current_quadtree_node, m_document.GetQuadTree().nodes[m_current_quadtree_node].object_begin,
-                               m_document.GetQuadTree().nodes[m_current_quadtree_node].object_end);
+
+       m_screen.DebugFontPrintF("Current View QuadTree");
+       QuadTreeIndex overlay = m_current_quadtree_node;
+       while (overlay != -1)
+       {
+               m_screen.DebugFontPrintF(" Node: %d (objs: %d -> %d)", overlay, m_document.GetQuadTree().nodes[overlay].object_begin,
+                                       m_document.GetQuadTree().nodes[overlay].object_end);
+               overlay = m_document.GetQuadTree().nodes[overlay].next_overlay;
+       }
+       m_screen.DebugFontPrintF("\n");
 
        Rect view_top_bounds = m_bounds;
        QuadTreeIndex tmp = m_current_quadtree_node;
@@ -285,7 +293,12 @@ void View::RenderQuadtreeNode(int width, int height, QuadTreeIndex node, int rem
        if (!remaining_depth) return;
        //Debug("Rendering QT node %d, (objs: %d -- %d)\n", node, m_document.GetQuadTree().nodes[node].object_begin, m_document.GetQuadTree().nodes[node].object_end);
        m_bounds_dirty = true;
-       RenderRange(width, height, m_document.GetQuadTree().nodes[node].object_begin, m_document.GetQuadTree().nodes[node].object_end);
+       QuadTreeIndex overlay = node;
+       while(overlay != -1)
+       {
+               RenderRange(width, height, m_document.GetQuadTree().nodes[overlay].object_begin, m_document.GetQuadTree().nodes[overlay].object_end);
+               overlay = m_document.GetQuadTree().nodes[overlay].next_overlay;
+       }
 
        if (m_bounds.Intersects(Rect(-1,-1,1,1)))
        {