Automatically generate quadtree children.
authorDavid Gow <david@ingeniumdigital.com>
Wed, 13 Aug 2014 11:49:33 +0000 (19:49 +0800)
committerDavid Gow <david@ingeniumdigital.com>
Wed, 13 Aug 2014 11:49:33 +0000 (19:49 +0800)
This mostly works, and does the view reparenting. It doesn't do any clipping,
so we still hit precision issues as (for example) b├ęzier control points are
outside the quadtree node's coordinate system, and become very, very large.

There are some issues with the boundaries of quadtree nodes, as the system
currently can't display two nodes at once. To compensate, it traverses up the
tree until it finds a single node which contains both, though this will be
a distant anscestor if the nodes are distantly related.

Quadtrees are still disabled by default. There are also a couple of minor
changes to the GL code to make it spit out fewer error messages and run
slightly faster on some hardware.

src/document.cpp
src/graphicsbuffer.cpp
src/quadtree.cpp
src/quadtree.h
src/screen.cpp
src/view.cpp

index 9d9011e..e684f3e 100644 (file)
@@ -107,8 +107,9 @@ QuadTreeIndex Document::GenQuadChild(QuadTreeIndex parent, QuadTreeNodeChildren
        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)
        {
-               if (ContainedInQuadChild(m_objects.bounds[i], type))
+               if (IntersectsQuadChild(m_objects.bounds[i], type))
                {
+                       Debug("Adding %s -> %s", m_objects.bounds[i].Str().c_str(), TransformToQuadChild(m_objects.bounds[i], type).Str().c_str());
                        m_objects.bounds.push_back(TransformToQuadChild(m_objects.bounds[i], type));
                        m_objects.types.push_back(m_objects.types[i]);
                        m_objects.data_indices.push_back(m_objects.data_indices[i]);
index 91c3478..217fa9a 100644 (file)
@@ -243,13 +243,14 @@ void GraphicsBuffer::UploadRange(size_t length, intptr_t offset, const void* dat
 
 void GraphicsBuffer::Resize(size_t length)
 {
-       glPushDebugGroup(GL_DEBUG_SOURCE_APPLICATION, 0, -1, "Resizing buffer.");
        if (m_invalidated)
        {
                m_buffer_size = length;
        }
        else
        {
+               glPushDebugGroup(GL_DEBUG_SOURCE_APPLICATION, 0, -1, "Resizing buffer.");
+               glDebugMessageControl(GL_DONT_CARE, GL_DONT_CARE, GL_DEBUG_SEVERITY_HIGH, 0, NULL, GL_TRUE);
                // Create a new buffer and copy the old data into it.
                UnMap();
                GLuint old_buffer = m_buffer_handle;    
@@ -260,8 +261,8 @@ void GraphicsBuffer::Resize(size_t length)
                glCopyBufferSubData(GL_COPY_READ_BUFFER, GL_COPY_WRITE_BUFFER, 0, 0, m_buffer_size);
                glDeleteBuffers(1, &old_buffer);
                m_buffer_size = length;
+               glPopDebugGroup();
        }
-       glPopDebugGroup();
 }
 
 void GraphicsBuffer::Bind() const
index 04630b7..2aace7a 100644 (file)
@@ -24,10 +24,6 @@ Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 {
        Rect dst = src;
-       dst.x *= 0.5;
-       dst.y *= 0.5;
-       dst.w *= 0.5;
-       dst.h *= 0.5;
        if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
        {
                dst.y += 1;
@@ -36,10 +32,14 @@ Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        {
                dst.x += 1;
        }
+       dst.x *= 0.5;
+       dst.y *= 0.5;
+       dst.w *= 0.5;
+       dst.h *= 0.5;
        return dst;
 }
 
-bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
+bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 {
        Rect std = {0,0,1,1};
        Rect dst = TransformFromQuadChild(std, child_type);
@@ -47,6 +47,19 @@ bool ContainedInQuadChild(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());
+       return true;
+}
+
+bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
+{
+       Rect std = {0,0,1,1};
+       Rect dst = TransformFromQuadChild(std, child_type);
+       if (src.x < dst.x) return false;
+       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());
        return true;
 }
 
index 61f0a1b..1443650 100644 (file)
@@ -50,6 +50,7 @@ namespace IPDF
 
        Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
        Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
+       bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
        bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
 }
 
index c183bf6..27675d5 100644 (file)
@@ -16,6 +16,8 @@ using namespace std;
 
 static void opengl_debug_callback(GLenum source, GLenum type, GLuint id, GLenum severity, GLsizei length, const GLchar* msg, const void *data)
 {
+       // Don't print out gl Errors we generated.
+       if (source == GL_DEBUG_SOURCE_APPLICATION) return;
        Error("OpenGL Error (%d): %s", id, msg);
 }
 
index 749df66..8b1857d 100644 (file)
@@ -37,7 +37,7 @@ View::View(Document & document, Screen & screen, const Rect & bounds, const Colo
 
 
 #ifndef QUADTREE_DISABLED
-       m_quadtree_max_depth = 2;
+       m_quadtree_max_depth = 1;
        m_current_quadtree_node = document.GetQuadTree().root_id;
 #endif
 }
@@ -151,18 +151,62 @@ void View::Render(int width, int height)
 #ifndef QUADTREE_DISABLED
        if (m_bounds_dirty)
        {
-               if (ContainedInQuadChild(m_bounds, QTC_TOP_LEFT) && m_document.GetQuadTree().nodes[m_current_quadtree_node].top_left != QUADTREE_EMPTY)
+               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)
+                       {
+                               m_bounds = TransformFromQuadChild(m_bounds, m_document.GetQuadTree().nodes[m_current_quadtree_node].child_type);
+                               m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].parent;
+                       }
+               }
+               if (ContainedInQuadChild(m_bounds, QTC_TOP_LEFT))
+               {
+                       if (m_document.GetQuadTree().nodes[m_current_quadtree_node].top_left == QUADTREE_EMPTY)
+                       {
+                               // We want to reparent into a child node, but none exist. Get the document to create one.
+                               m_document.GenQuadChild(m_current_quadtree_node, QTC_TOP_LEFT);
+                               m_render_dirty = true;
+                       }
                        m_bounds = TransformToQuadChild(m_bounds, QTC_TOP_LEFT);
                        m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].top_left;
                }
-               if ((m_bounds.w > 1 || m_bounds.h > 1) && m_document.GetQuadTree().nodes[m_current_quadtree_node].parent != QUADTREE_EMPTY)
+               if (ContainedInQuadChild(m_bounds, QTC_TOP_RIGHT))
+               {
+                       if (m_document.GetQuadTree().nodes[m_current_quadtree_node].top_right == QUADTREE_EMPTY)
+                       {
+                               // We want to reparent into a child node, but none exist. Get the document to create one.
+                               m_document.GenQuadChild(m_current_quadtree_node, QTC_TOP_RIGHT);
+                               m_render_dirty = true;
+                       }
+                       m_bounds = TransformToQuadChild(m_bounds, QTC_TOP_RIGHT);
+                       m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].top_right;
+               }
+               if (ContainedInQuadChild(m_bounds, QTC_BOTTOM_LEFT))
+               {
+                       if (m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_left == QUADTREE_EMPTY)
+                       {
+                               // We want to reparent into a child node, but none exist. Get the document to create one.
+                               m_document.GenQuadChild(m_current_quadtree_node, QTC_BOTTOM_LEFT);
+                               m_render_dirty = true;
+                       }
+                       m_bounds = TransformToQuadChild(m_bounds, QTC_BOTTOM_LEFT);
+                       m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_left;
+               }
+               if (ContainedInQuadChild(m_bounds, QTC_BOTTOM_RIGHT))
                {
-                       m_bounds = TransformFromQuadChild(m_bounds, m_document.GetQuadTree().nodes[m_current_quadtree_node].child_type);
-                       m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].parent;
+                       if (m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right == QUADTREE_EMPTY)
+                       {
+                               // We want to reparent into a child node, but none exist. Get the document to create one.
+                               m_document.GenQuadChild(m_current_quadtree_node, QTC_BOTTOM_RIGHT);
+                               m_render_dirty = true;
+                       }
+                       m_bounds = TransformToQuadChild(m_bounds, QTC_BOTTOM_RIGHT);
+                       m_current_quadtree_node = m_document.GetQuadTree().nodes[m_current_quadtree_node].bottom_right;
                }
        }
-       m_screen.DebugFontPrintF("Current View QuadTree Node: %d\n", m_current_quadtree_node);
+       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);
 #endif
 
        if (!m_use_gpu_rendering)
@@ -293,11 +337,11 @@ void View::UpdateObjBoundsVBO(unsigned first_obj, unsigned last_obj)
        }
        else
        {
-               m_objbounds_vbo.SetUsage(GraphicsBuffer::BufferUsageDynamicDraw);
+               m_objbounds_vbo.SetUsage(GraphicsBuffer::BufferUsageDynamicCopy);
        }
        m_objbounds_vbo.Resize(m_document.ObjectCount()*sizeof(GPUObjBounds));
 
-       BufferBuilder<GPUObjBounds> obj_bounds_builder(m_objbounds_vbo.MapRange(first_obj*sizeof(GPUObjBounds), (last_obj-first_obj)*sizeof(GPUObjBounds), false, true, false), m_objbounds_vbo.GetSize());
+       BufferBuilder<GPUObjBounds> obj_bounds_builder(m_objbounds_vbo.MapRange(first_obj*sizeof(GPUObjBounds), (last_obj-first_obj)*sizeof(GPUObjBounds), false, true, true), m_objbounds_vbo.GetSize());
 
        for (unsigned id = first_obj; id < last_obj; ++id)
        {

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