[cogl/wip/journal-reorg: 2/2] cogl-journal: Use a loose region instead of a bounding box

[Neil Roberts <nroberts src gnome org>]

commit c1602f4abcf9083fde25c8e576d019f30cf192fb
Author: Neil Roberts <neil linux intel com>
Date:   Tue Sep 27 15:32:58 2011 +0100

    cogl-journal: Use a loose region instead of a bounding box
    
    Instead of just recording the bounding box of a journal batch, it now
    uses a new data type called a loose region. A loose region keeps track
    of up to 4 separate bounding boxes to represent at least the region
    covered by the batch. If a new rectangle added to the region only
    increases the size of an existing bounding box to within a certain
    threshold then it will be added to that bounding box, otherwise it
    will start a new bounding box. This increases the chances that batches
    can be grouped together because it can represent sparse regions to a
    degree without as much of the complexity as totally accurately
    tracking the region.

 cogl/Makefile.am            |    2 +
 cogl/cogl-journal-private.h |    6 +-
 cogl/cogl-journal.c         |   49 +++++----------
 cogl/cogl-loose-region.c    |  140 +++++++++++++++++++++++++++++++++++++++++++
 cogl/cogl-loose-region.h    |   64 ++++++++++++++++++++
 5 files changed, 226 insertions(+), 35 deletions(-)
---
diff --git a/cogl/Makefile.am b/cogl/Makefile.am
index f12354f..7968a5a 100644
--- a/cogl/Makefile.am
+++ b/cogl/Makefile.am
@@ -313,6 +313,8 @@ cogl_sources_c = \
 	$(srcdir)/cogl-gtype-private.h                  \
 	$(srcdir)/cogl-point-in-poly-private.h       	\
 	$(srcdir)/cogl-point-in-poly.c       		\
+	$(srcdir)/cogl-loose-region.h			\
+	$(srcdir)/cogl-loose-region.c			\
 	$(srcdir)/cogl-clutter.c       			\
 	$(srcdir)/winsys/cogl-winsys-stub-private.h	\
 	$(srcdir)/cogl-queue.h				\
diff --git a/cogl/cogl-journal-private.h b/cogl/cogl-journal-private.h
index 2b7cbb3..5ac52e5 100644
--- a/cogl/cogl-journal-private.h
+++ b/cogl/cogl-journal-private.h
@@ -28,6 +28,7 @@
 #include "cogl-handle.h"
 #include "cogl-clip-stack.h"
 #include "cogl-queue.h"
+#include "cogl-loose-region.h"
 
 #define COGL_JOURNAL_VBO_POOL_SIZE 8
 
@@ -66,9 +67,8 @@ typedef struct _CoglJournalBatch
   CoglPipeline *pipeline;
   /* List of entries */
   CoglJournalEntryList entries;
-  /* The bounding box of this batch in screen space */
-  float bounds_x1, bounds_y1;
-  float bounds_x2, bounds_y2;
+  /* The region covered by this batch in screen space */
+  CoglLooseRegion region;
 } CoglJournalBatch;
 
 /* To improve batching of geometry when submitting vertices to OpenGL we
diff --git a/cogl/cogl-journal.c b/cogl/cogl-journal.c
index be37374..f7c6b2d 100644
--- a/cogl/cogl-journal.c
+++ b/cogl/cogl-journal.c
@@ -1578,7 +1578,7 @@ _cogl_journal_add_entry_to_batch (CoglJournal *journal,
                                   CoglPipeline *pipeline,
                                   CoglJournalEntry *entry)
 {
-  float bounds_x1, bounds_y1, bounds_x2, bounds_y2;
+  CoglLooseRegionRectangle bounds;
   int batch_index;
   CoglJournalBatch *batch;
   float poly[16];
@@ -1587,21 +1587,21 @@ _cogl_journal_add_entry_to_batch (CoglJournal *journal,
   /* Calculate the screen-space bounding box of this entry */
   entry_to_screen_polygon (entry, poly);
 
-  bounds_x2 = bounds_x1 = poly[0];
-  bounds_y2 = bounds_y1 = poly[1];
+  bounds.x_2 = bounds.x_1 = poly[0];
+  bounds.y_2 = bounds.y_1 = poly[1];
 
   for (i = 1; i < 4; i++)
     {
       float x = poly[i * 4 + 0], y = poly[i * 4 + 1];
 
-      if (x < bounds_x1)
-        bounds_x1 = x;
-      if (y < bounds_y1)
-        bounds_y1 = y;
-      if (x > bounds_x2)
-        bounds_x2 = x;
-      if (y > bounds_y2)
-        bounds_y2 = y;
+      if (x < bounds.x_1)
+        bounds.x_1 = x;
+      if (y < bounds.y_1)
+        bounds.y_1 = y;
+      if (x > bounds.x_2)
+        bounds.x_2 = x;
+      if (y > bounds.y_2)
+        bounds.y_2 = y;
     }
 
   /* Search backwards through the list of lists for a matching
@@ -1620,27 +1620,13 @@ _cogl_journal_add_entry_to_batch (CoglJournal *journal,
                                  ~COGL_PIPELINE_STATE_COLOR),
                                 COGL_PIPELINE_LAYER_STATE_ALL,
                                 0))
-        {
-          /* We have a matching list so we can just append this entry */
-          if (bounds_x1 < batch->bounds_x1)
-            batch->bounds_x1 = bounds_x1;
-          if (bounds_x2 > batch->bounds_x2)
-            batch->bounds_x2 = bounds_x2;
-          if (bounds_y1 < batch->bounds_y1)
-            batch->bounds_y1 = bounds_y1;
-          if (bounds_y2 > batch->bounds_y2)
-            batch->bounds_y2 = bounds_y2;
-
-          goto found_list;
-        }
+        /* We have a matching list so we can just append this entry */
+        goto found_list;
 
       /* Any further lists will be painted behind this one. Therefore
          we can only continue searching if the new entry does not
          intersect the current list */
-      if (bounds_x2 > batch->bounds_x1 &&
-          bounds_x1 < batch->bounds_x2 &&
-          bounds_y2 > batch->bounds_y1 &&
-          bounds_y1 < batch->bounds_y2)
+      if (_cogl_loose_region_intersects (&batch->region, &bounds))
         /* The new entry intersects the list so we can't paint behind
            this one and we'll have to start a new list */
         break;
@@ -1653,14 +1639,13 @@ _cogl_journal_add_entry_to_batch (CoglJournal *journal,
                           CoglJournalBatch, batch_index);
 
   batch->pipeline = _cogl_pipeline_journal_ref (pipeline);
-  batch->bounds_x1 = bounds_x1;
-  batch->bounds_y1 = bounds_y1;
-  batch->bounds_x2 = bounds_x2;
-  batch->bounds_y2 = bounds_y2;
+  _cogl_loose_region_init (&batch->region);
   COGL_TAILQ_INIT (&batch->entries);
 
 found_list:
 
+  _cogl_loose_region_add_rectangle (&batch->region, &bounds);
+
   COGL_TAILQ_INSERT_TAIL (&batch->entries, entry, batch);
 }
 
diff --git a/cogl/cogl-loose-region.c b/cogl/cogl-loose-region.c
new file mode 100644
index 0000000..20bf443
--- /dev/null
+++ b/cogl/cogl-loose-region.c
@@ -0,0 +1,140 @@
+/*
+ * Cogl
+ *
+ * An object oriented GL/GLES Abstraction/Utility Layer
+ *
+ * Copyright (C) 2011 Intel Corporation.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ *
+ * Authors:
+ *   Neil Roberts <neil linux intel com>
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <math.h>
+
+#include "cogl-loose-region.h"
+
+/* This specifies the fraction of the size of the new rectangle that
+   will permit a bounding box to grow by before we consider starting a
+   new bounding box. Eg, 1.1 means we'll allow the bounding box to
+   grow by the size of the rectangle + 10% waste */
+#define SIZE_INCREASE_THRESHOLD 2.0f
+
+void
+_cogl_loose_region_init (CoglLooseRegion *region)
+{
+  region->n_rects = 0;
+}
+
+static float
+_cogl_loose_region_get_size (const CoglLooseRegionRectangle *rect)
+{
+  float width = rect->x_2 - rect->x_1;
+  float height = rect->y_2 - rect->y_1;
+
+  return width * height;
+}
+
+static void
+_cogl_loose_region_union_rectangles (const CoglLooseRegionRectangle *a,
+                                     const CoglLooseRegionRectangle *b,
+                                     CoglLooseRegionRectangle *out)
+{
+  out->x_1 = MIN (a->x_1, b->x_1);
+  out->y_1 = MIN (a->y_1, b->y_1);
+  out->x_2 = MAX (a->x_2, b->x_2);
+  out->y_2 = MAX (a->y_2, b->y_2);
+}
+
+void
+_cogl_loose_region_add_rectangle (CoglLooseRegion *region,
+                                  const CoglLooseRegionRectangle *rect)
+{
+  int best_index = -1;
+  float best_increase = G_MAXFLOAT;
+  float rect_size;
+  int i;
+
+  rect_size = _cogl_loose_region_get_size (rect);
+
+  /* Look for an already existing bounding box that we can expand to
+     fit with the maximum threshold of the size increase */
+  for (i = 0; i < region->n_rects; i++)
+    {
+      CoglLooseRegionRectangle new_rectangle;
+      float size_increase;
+
+      _cogl_loose_region_union_rectangles (region->rects + i,
+                                           rect,
+                                           &new_rectangle);
+
+      size_increase = (_cogl_loose_region_get_size (&new_rectangle) -
+                       _cogl_loose_region_get_size (region->rects + i));
+
+      if (size_increase <= SIZE_INCREASE_THRESHOLD * rect_size)
+        {
+          /* We've found an acceptable bounding box so we'll stop
+             looking */
+          region->rects[i] = new_rectangle;
+          return;
+        }
+
+      if (size_increase < best_increase)
+        {
+          best_index = i;
+          best_increase = size_increase;
+        }
+    }
+
+  /* If we make it here then we didn't find a suitable existing
+     bounding box. If we can make a new one then we will, otherwise
+     we'll just add it to the best box */
+  if (region->n_rects < COGL_LOOSE_REGION_N_RECTANGLES)
+    region->rects[region->n_rects++] = *rect;
+  else
+    {
+      g_assert (best_index >= 0 && best_index < COGL_LOOSE_REGION_N_RECTANGLES);
+      _cogl_loose_region_union_rectangles (region->rects + best_index,
+                                           rect,
+                                           region->rects + best_index);
+    }
+}
+
+gboolean
+_cogl_loose_region_intersects (const CoglLooseRegion *region,
+                               const CoglLooseRegionRectangle *rect)
+{
+  int i;
+
+  for (i = 0; i < region->n_rects; i++)
+    {
+      const CoglLooseRegionRectangle *r_rect = region->rects + i;
+
+      if (rect->x_2 > r_rect->x_1 &&
+          rect->x_1 < r_rect->x_2 &&
+          rect->y_2 > r_rect->y_1 &&
+          rect->y_1 < r_rect->y_2)
+        return TRUE;
+    }
+
+  return FALSE;
+}
+
diff --git a/cogl/cogl-loose-region.h b/cogl/cogl-loose-region.h
new file mode 100644
index 0000000..b7296d4
--- /dev/null
+++ b/cogl/cogl-loose-region.h
@@ -0,0 +1,64 @@
+/*
+ * Cogl
+ *
+ * An object oriented GL/GLES Abstraction/Utility Layer
+ *
+ * Copyright (C) 2011 Intel Corporation.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library. If not, see <http://www.gnu.org/licenses/>.
+ *
+ *
+ *
+ * Authors:
+ *   Neil Roberts <neil linux intel com>
+ */
+
+/* CoglLooseRegion is a data structure that is a cross between a
+   simple bounding box and a region. Instead of keeping all of the
+   rectangles necessary to track an exact region, it only keeps around
+   a few bounding boxes. This can be checked for intersection much
+   more quickly than a complicated region but it will have some false
+   positives. */
+
+#ifndef __COGL_LOOSE_REGION_H__
+#define __COGL_LOOSE_REGION_H__
+
+#include <glib.h>
+
+#define COGL_LOOSE_REGION_N_RECTANGLES 4
+
+typedef struct _CoglLooseRegionRectangle
+{
+  float x_1, y_1;
+  float x_2, y_2;
+} CoglLooseRegionRectangle;
+
+typedef struct _CoglLooseRegion
+{
+  int n_rects;
+  CoglLooseRegionRectangle rects[COGL_LOOSE_REGION_N_RECTANGLES];
+} CoglLooseRegion;
+
+void
+_cogl_loose_region_init (CoglLooseRegion *region);
+
+void
+_cogl_loose_region_add_rectangle (CoglLooseRegion *region,
+                                  const CoglLooseRegionRectangle *rect);
+
+gboolean
+_cogl_loose_region_intersects (const CoglLooseRegion *region,
+                               const CoglLooseRegionRectangle *rect);
+
+#endif /* __COGL_LOOSE_REGION_H__ */