From 1a234dbfe3aaa80894807d1a9f4a2abeb3ad1411 Mon Sep 17 00:00:00 2001 From: David Gow Date: Sun, 5 Oct 2014 12:29:14 +0800 Subject: [PATCH] Adding things to quadtree is implemented but segfaulty. (i.e. it segfaults all of the time, and even if it didn't, it'd crash if you zoomed in, and also you can still only add things to node 0 and really this breaks a lot more than it fixes) For the prosecution, segfaults except: - When run in valgrind - When run in gdb on nvidia hardware Infinite loops when: - You zoom in, zoom out, add an object, and zoom in again. --- src/document.cpp | 109 ++++++++++++++++++++++++++++++++++++----- src/document.h | 2 + src/graphicsbuffer.cpp | 25 ++++++++-- src/objectrenderer.h | 2 +- src/quadtree.h | 2 + 5 files changed, 125 insertions(+), 15 deletions(-) diff --git a/src/document.cpp b/src/document.cpp index 7dda475..ffe3b8a 100644 --- a/src/document.cpp +++ b/src/document.cpp @@ -184,6 +184,8 @@ QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren } } m_quadtree.nodes[new_index].object_end = m_objects.bounds.size(); + // No objects are dirty. + m_quadtree.nodes[new_index].object_dirty = m_objects.bounds.size(); switch (type) { case QTC_TOP_LEFT: @@ -204,6 +206,80 @@ QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren return new_index; } +void Document::OverlayQuadChildren(QuadTreeIndex orig_parent, QuadTreeIndex parent, QuadTreeNodeChildren type) +{ + QuadTreeIndex new_index = m_quadtree.nodes.size(); + Debug("-------------- Generating Quadtree Node %d (orig %d parent %d, type %d) ----------------------", new_index, orig_parent, parent, type); + m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, orig_parent, type, 0, 0, -1}); + + m_quadtree.nodes[new_index].object_begin = m_objects.bounds.size(); + for (unsigned i = m_quadtree.nodes[parent].object_dirty; i < m_quadtree.nodes[parent].object_end; ++i) + { + if (IntersectsQuadChild(m_objects.bounds[i], type)) + { + m_count += ClipObjectToQuadChild(i, type); + } + } + m_quadtree.nodes[new_index].object_end = m_objects.bounds.size(); + QuadTreeIndex orig_node = -1; + switch (type) + { + case QTC_TOP_LEFT: + orig_node = m_quadtree.nodes[orig_parent].top_left = new_index; + break; + case QTC_TOP_RIGHT: + orig_node = m_quadtree.nodes[orig_parent].top_right = new_index; + break; + case QTC_BOTTOM_LEFT: + orig_node = m_quadtree.nodes[orig_parent].bottom_left = new_index; + break; + case QTC_BOTTOM_RIGHT: + orig_node = m_quadtree.nodes[orig_parent].bottom_right = new_index; + break; + default: + Fatal("Tried to overlay a QuadTree child of invalid type!"); + } + if (orig_node == -1) + Fatal("Tried to overlay a QuadTree child that didn't exist!"); + + // Add us to the node's overlay linked list. + QuadTreeIndex prev_overlay = orig_node; + while (m_quadtree.nodes[prev_overlay].next_overlay != -1); + m_quadtree.nodes[prev_overlay].next_overlay = new_index; + + // Recurse into any extant children. + if (m_quadtree.nodes[orig_node].top_left != -1) + OverlayQuadChildren(orig_node, new_index, QTC_TOP_LEFT); + if (m_quadtree.nodes[orig_node].top_right != -1) + OverlayQuadChildren(orig_node, new_index, QTC_TOP_RIGHT); + if (m_quadtree.nodes[orig_node].bottom_left != -1) + OverlayQuadChildren(orig_node, new_index, QTC_BOTTOM_LEFT); + if (m_quadtree.nodes[orig_node].bottom_right != -1) + OverlayQuadChildren(orig_node, new_index, QTC_BOTTOM_RIGHT); + + m_quadtree.nodes[new_index].object_dirty = m_quadtree.nodes[new_index].object_end; +} + +void Document::PropagateQuadChanges(QuadTreeIndex node) +{ + for(QuadTreeIndex overlay = node; overlay != -1; overlay = m_quadtree.nodes[overlay].next_overlay) + { + // We don't care about clean overlays. + if (m_quadtree.nodes[overlay].object_dirty == m_quadtree.nodes[overlay].object_end) continue; + // Recurse into any extant children. + if (m_quadtree.nodes[node].top_left != -1) + OverlayQuadChildren(node, overlay, QTC_TOP_LEFT); + if (m_quadtree.nodes[node].top_right != -1) + OverlayQuadChildren(node, overlay, QTC_TOP_RIGHT); + if (m_quadtree.nodes[node].bottom_left != -1) + OverlayQuadChildren(node, overlay, QTC_BOTTOM_LEFT); + if (m_quadtree.nodes[node].bottom_right != -1) + OverlayQuadChildren(node, overlay, QTC_BOTTOM_RIGHT); + + m_quadtree.nodes[overlay].object_dirty = m_quadtree.nodes[overlay].object_end; + } +} + // Reparent a quadtree node, making it the "type" child of a new node. QuadTreeIndex Document::GenQuadParent(QuadTreeIndex child, QuadTreeNodeChildren type) { @@ -222,6 +298,7 @@ QuadTreeIndex Document::GenQuadParent(QuadTreeIndex child, QuadTreeNodeChildren } } m_quadtree.nodes[new_index].object_end = m_objects.bounds.size(); + m_quadtree.nodes[new_index].object_dirty = m_objects.bounds.size(); switch (type) { case QTC_TOP_LEFT: @@ -340,24 +417,34 @@ unsigned Document::Add(ObjectType type, const Rect & bounds, unsigned data_index #ifndef QUADTREE_DISABLED if (qti != -1) { - while (m_quadtree.nodes[qti].next_overlay != -1) + QuadTreeIndex new_qti = qti; + while (m_quadtree.nodes[new_qti].next_overlay != -1) { - if (m_count == m_quadtree.nodes[qti].object_end+1) + if (m_count == m_quadtree.nodes[new_qti].object_end+1) { - m_quadtree.nodes[qti].object_end++; + m_quadtree.nodes[new_qti].object_end++; goto done; } - qti = m_quadtree.nodes[qti].next_overlay; + new_qti = m_quadtree.nodes[new_qti].next_overlay; } - 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; + { + QuadTreeIndex overlay = m_quadtree.nodes.size(); + Debug("Adding new overlay, nqti = %d, overlay = %d", new_qti, overlay); + m_quadtree.nodes.push_back(m_quadtree.nodes[qti]); + m_quadtree.nodes[overlay].object_begin = m_count; + // All objects are dirty. + m_quadtree.nodes[overlay].object_dirty = m_count; + m_quadtree.nodes[overlay].object_end = m_count+1; + m_quadtree.nodes[overlay].next_overlay = -1; + m_quadtree.nodes[new_qti].next_overlay = overlay; + new_qti = overlay; + } +done: + m_count++; + PropagateQuadChanges(qti); } #endif -done: - return (m_count++); // Why can't we just use the size of types or something? + return m_count; // Why can't we just use the size of types or something? } unsigned Document::AddBezierData(const Bezier & bezier) diff --git a/src/document.h b/src/document.h index d67b0b2..94be6cc 100644 --- a/src/document.h +++ b/src/document.h @@ -90,6 +90,8 @@ namespace IPDF inline const QuadTree& GetQuadTree() { if (m_quadtree.root_id == QUADTREE_EMPTY) { GenBaseQuadtree(); } return m_quadtree; } QuadTreeIndex GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren type); QuadTreeIndex GenQuadParent(QuadTreeIndex child, QuadTreeNodeChildren mytype); + void OverlayQuadChildren(QuadTreeIndex orig_parent, QuadTreeIndex parent, QuadTreeNodeChildren type); + void PropagateQuadChanges(QuadTreeIndex node); // Returns the number of objects the current object formed when clipped, the objects in question are added to the end of the document. int ClipObjectToQuadChild(int object_id, QuadTreeNodeChildren type); #endif diff --git a/src/graphicsbuffer.cpp b/src/graphicsbuffer.cpp index 844dfe8..c3d9620 100644 --- a/src/graphicsbuffer.cpp +++ b/src/graphicsbuffer.cpp @@ -130,11 +130,13 @@ bool GraphicsBuffer::RecreateBuffer(const void *data) { glDeleteBuffers(1, &m_buffer_handle); } - glGenBuffers(1, &m_buffer_handle); - glObjectLabel(GL_BUFFER, m_buffer_handle, -1, m_name); - m_buffer_shape_dirty = false; if (m_buffer_size) + { + glGenBuffers(1, &m_buffer_handle); + glObjectLabel(GL_BUFFER, m_buffer_handle, -1, m_name); + m_buffer_shape_dirty = false; Upload(m_buffer_size, data); + } return true; } @@ -156,6 +158,10 @@ void* GraphicsBuffer::Map(bool read, bool write, bool invalidate) if (m_map_pointer) Warn("Tried to map already mapped buffer!"); + // Intel really doesn't seem to like this. + if (!m_buffer_size) + return (m_map_pointer = 0); + if (!read && m_buffer_usage == BufferUsage::BufferUsageStaticDraw) { @@ -181,6 +187,10 @@ void* GraphicsBuffer::MapRange(int offset, int length, bool read, bool write, bo if (m_map_pointer) Warn("Tried to map already mapped buffer!"); + // This sometimes makes Intel corrupt memory? + if (!length) return (m_map_pointer = 0); + + RecreateBuffer(); Bind(); @@ -243,10 +253,19 @@ void GraphicsBuffer::UploadRange(size_t length, intptr_t offset, const void* dat void GraphicsBuffer::Resize(size_t length) { + if (!m_buffer_size) + { + m_buffer_size = length; + return; + } if (m_invalidated && m_buffer_size >= length) { m_buffer_size = length; } + else if (length <= m_buffer_size) + { + // Don't need to do anything. + } else { glPushDebugGroup(GL_DEBUG_SOURCE_APPLICATION, 0, -1, "Resizing buffer."); diff --git a/src/objectrenderer.h b/src/objectrenderer.h index 85a413b..ebb532e 100644 --- a/src/objectrenderer.h +++ b/src/objectrenderer.h @@ -167,7 +167,7 @@ namespace IPDF class PathRenderer : public ObjectRenderer { public: - PathRenderer() : ObjectRenderer(PATH, "shaders/rect_vert.glsl", "shaders/rect_frag.glsl", "shaders/bezier_texbug_geom.glsl") {} + PathRenderer() : ObjectRenderer(PATH, "shaders/rect_vert.glsl", "shaders/rect_frag.glsl", "shaders/bezier_texbuf_geom.glsl") {} virtual ~PathRenderer() {} virtual void RenderUsingCPU(Objects & objects, const View & view, const CPURenderTarget & target, unsigned first_obj_id, unsigned last_obj_id); // do nothing on GPU diff --git a/src/quadtree.h b/src/quadtree.h index e35da2e..15fd8a9 100644 --- a/src/quadtree.h +++ b/src/quadtree.h @@ -42,6 +42,8 @@ namespace IPDF unsigned object_end; // Linked list of "extra" nodes QuadTreeIndex next_overlay; + // First object which has not yet been propagated to extant children/parent. + unsigned object_dirty; }; struct QuadTree -- 2.20.1