From: David Gow Date: Wed, 24 Sep 2014 13:05:04 +0000 (+0800) Subject: Some quadtree stuff: bugfix + mutation X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=commitdiff_plain;h=c29180e78e8a6e16145d308a4e06e874bc29ccfb Some quadtree stuff: bugfix + mutation --- diff --git a/src/bezier.cpp b/src/bezier.cpp index 99611dc..67b384c 100644 --- a/src/bezier.cpp +++ b/src/bezier.cpp @@ -54,9 +54,11 @@ static void CubicSolveSegment(vector & 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 SolveCubic(const Real & a, const Real & b, const Real & c, const Re Real tu(max); Real tl(min); vector 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 --- a/src/bezier.h +++ b/src/bezier.h @@ -15,7 +15,7 @@ namespace IPDF extern std::vector SolveQuadratic(const Real & a, const Real & b, const Real & c, const Real & min = 0, const Real & max = 1); - extern std::vector 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 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 x_intersection = SolveXParam(r.x); + Debug("Found %d intersections on left edge", x_intersection.size()); // And for the other side. std::vector 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 y_intersection = SolveYParam(r.y); + Debug("Found %d intersections on top edge", y_intersection.size()); std::vector 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 --- 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 --- 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 --- 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 --- 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" /> - + sodipodi:nodetypes="cc" />--> diff --git a/src/view.cpp b/src/view.cpp index 52a4c6d..2b21225 100644 --- 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))) {