diff options
author | Neil Roberts <neil@linux.intel.com> | 2011-09-27 15:32:58 +0100 |
---|---|---|
committer | Neil Roberts <neil@linux.intel.com> | 2011-09-27 16:08:42 +0100 |
commit | c1602f4abcf9083fde25c8e576d019f30cf192fb (patch) | |
tree | 62296ff5b4538a79752a174599dc6d3624ed4262 | |
parent | 7bd66f40ca3fa01ec49ebe2d87a76c26874bacd7 (diff) | |
download | cogl-wip/journal-reorg.tar.gz |
cogl-journal: Use a loose region instead of a bounding boxwip/journal-reorg
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.
-rw-r--r-- | cogl/Makefile.am | 2 | ||||
-rw-r--r-- | cogl/cogl-journal-private.h | 6 | ||||
-rw-r--r-- | cogl/cogl-journal.c | 49 | ||||
-rw-r--r-- | cogl/cogl-loose-region.c | 140 | ||||
-rw-r--r-- | cogl/cogl-loose-region.h | 64 |
5 files changed, 226 insertions, 35 deletions
diff --git a/cogl/Makefile.am b/cogl/Makefile.am index f12354f5..7968a5ad 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 2b7cbb3b..5ac52e53 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 be37374d..f7c6b2da 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 00000000..20bf4431 --- /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 00000000..b7296d44 --- /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__ */ |