scenegraph: added a region utility class

4 files changed, 2360 insertions, 2 deletions

diff --git a/src/Makefile_Ector.am b/src/Makefile_Ector.am
index bed5ffbdd8..647d73357a 100644
--- a/src/Makefile_Ector.am
+++ b/src/Makefile_Ector.am
@@ -124,6 +124,8 @@ static_libs/scenegraph/sg_renderer.h \
 static_libs/scenegraph/sg_context.h \
 static_libs/scenegraph/utils/sg_thread.h \
 static_libs/scenegraph/utils/sg_thread.c \
+static_libs/scenegraph/utils/sg_region.h \
+static_libs/scenegraph/utils/sg_region.c \
 static_libs/scenegraph/software/sg_software_context.c \
 static_libs/scenegraph/software/sg_software_context.h \
 $(NULL)
diff --git a/src/static_libs/scenegraph/Scenegraph.h b/src/static_libs/scenegraph/Scenegraph.h
index 271eec3b95..f02ad0ece1 100644
--- a/src/static_libs/scenegraph/Scenegraph.h
+++ b/src/static_libs/scenegraph/Scenegraph.h
@@ -34,8 +34,7 @@ extern "C" {
 #endif
 
 #include "sg_node.h"
-
-
+#include "utils/sg_region.h"
 
 #ifdef __cplusplus
 }
diff --git a/src/static_libs/scenegraph/utils/sg_region.c b/src/static_libs/scenegraph/utils/sg_region.c
new file mode 100644
index 0000000000..de5681edc7
--- /dev/null
+++ b/src/static_libs/scenegraph/utils/sg_region.c
@@ -0,0 +1,2316 @@
+/*
+ * Copyright 1987, 1988, 1989, 1998  The Open Group
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation.
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+ * OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
+ * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * Except as contained in this notice, the name of The Open Group shall not be
+ * used in advertising or otherwise to promote the sale, use or other dealings
+ * in this Software without prior written authorization from The Open Group.
+ *
+ * Copyright 1987, 1988, 1989 by
+ * Digital Equipment Corporation, Maynard, Massachusetts.
+ *
+ *                    All Rights Reserved
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation for any purpose and without fee is hereby granted,
+ * provided that the above copyright notice appear in all copies and that
+ * both that copyright notice and this permission notice appear in
+ * supporting documentation, and that the name of Digital not be
+ * used in advertising or publicity pertaining to distribution of the
+ * software without specific, written prior permission.
+ *
+ * DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
+ * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
+ * DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
+ * ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
+ * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
+ * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
+ * SOFTWARE.
+ *
+ * Copyright © 1998 Keith Packard
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Keith Packard not be used in
+ * advertising or publicity pertaining to distribution of the software without
+ * specific, written prior permission.  Keith Packard makes no
+ * representations about the suitability of this software for any purpose.  It
+ * is provided "as is" without express or implied warranty.
+ *
+ * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
+ * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
+ * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
+ * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
+ * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+ * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+ * PERFORMANCE OF THIS SOFTWARE.
+ */
+#include "sg_region.h"
+
+#include <stdlib.h>
+#include <limits.h>
+#include <string.h>
+#include <stdio.h>
+#include <assert.h>
+
+#define critical_if_fail assert
+
+#define PIXMAN_EXPORT static
+#define FALSE 0
+#define TRUE 1
+#define FUNC ""
+
+typedef int pixman_bool_t;
+
+typedef struct pixman_rectangle	pixman_rectangle_t;
+
+typedef struct pixman_box		     box_type_t;
+typedef struct pixman_region_data	 region_data_type_t;
+typedef struct pixman_region	     region_type_t;
+typedef int64_t                      overflow_int_t;
+
+#define PREFIX(x) pixman_region##x
+
+#define PIXMAN_REGION_MAX INT32_MAX
+#define PIXMAN_REGION_MIN INT32_MIN
+
+
+typedef struct {
+    int x, y;
+} point_type_t;
+
+struct pixman_region_data {
+    long		size;
+    long		numRects;
+/*  box_type_t	rects[size];   in memory but not explicitly declared */
+};
+
+struct pixman_rectangle
+{
+    int32_t x, y;
+    uint32_t width, height;
+};
+
+struct pixman_box
+{
+    int32_t x1, y1, x2, y2;
+};
+
+struct pixman_region
+{
+    box_type_t          extents;
+    region_data_type_t  *data;
+};
+
+typedef enum
+{
+    PIXMAN_REGION_OUT,
+    PIXMAN_REGION_IN,
+    PIXMAN_REGION_PART
+} pixman_region_overlap_t;
+
+static void
+_pixman_log_error (const char *function, const char *message)
+{
+    fprintf (stderr,
+         "*** BUG ***\n"
+         "In %s: %s\n"
+         "Set a breakpoint on '_pixman_log_error' to debug\n\n",
+                 function, message);
+}
+
+
+
+#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
+/* not a region */
+#define PIXREGION_NAR(reg)      ((reg)->data == pixman_broken_data)
+#define PIXREGION_NUMRECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
+#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
+#define PIXREGION_RECTS(reg) \
+    ((reg)->data ? (box_type_t *)((reg)->data + 1) \
+     : &(reg)->extents)
+#define PIXREGION_BOXPTR(reg) ((box_type_t *)((reg)->data + 1))
+#define PIXREGION_BOX(reg, i) (&PIXREGION_BOXPTR (reg)[i])
+#define PIXREGION_TOP(reg) PIXREGION_BOX (reg, (reg)->data->numRects)
+#define PIXREGION_END(reg) PIXREGION_BOX (reg, (reg)->data->numRects - 1)
+
+#define GOOD_RECT(rect) ((rect)->x1 < (rect)->x2 && (rect)->y1 < (rect)->y2)
+#define BAD_RECT(rect) ((rect)->x1 > (rect)->x2 || (rect)->y1 > (rect)->y2)
+
+#ifdef DEBUG
+
+#define GOOD(reg)							\
+    do									\
+    {									\
+    if (!PREFIX (_selfcheck (reg)))					\
+        _pixman_log_error (FUNC, "Malformed region " # reg);	\
+    } while (0)
+
+#else
+
+#define GOOD(reg)
+
+#endif
+
+static const box_type_t PREFIX (_empty_box_) = { 0, 0, 0, 0 };
+static const region_data_type_t PREFIX (_empty_data_) = { 0, 0 };
+#if defined (__llvm__) && !defined (__clang__)
+static const volatile region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
+#else
+static const region_data_type_t PREFIX (_broken_data_) = { 0, 0 };
+#endif
+
+static box_type_t *pixman_region_empty_box =
+    (box_type_t *)&PREFIX (_empty_box_);
+static region_data_type_t *pixman_region_empty_data =
+    (region_data_type_t *)&PREFIX (_empty_data_);
+static region_data_type_t *pixman_broken_data =
+    (region_data_type_t *)&PREFIX (_broken_data_);
+
+static pixman_bool_t
+pixman_break (region_type_t *region);
+
+/*
+ * The functions in this file implement the Region abstraction used extensively
+ * throughout the X11 sample server. A Region is simply a set of disjoint
+ * (non-overlapping) rectangles, plus an "extent" rectangle which is the
+ * smallest single rectangle that contains all the non-overlapping rectangles.
+ *
+ * A Region is implemented as a "y-x-banded" array of rectangles.  This array
+ * imposes two degrees of order.  First, all rectangles are sorted by top side
+ * y coordinate first (y1), and then by left side x coordinate (x1).
+ *
+ * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
+ * band has the same top y coordinate (y1), and each has the same bottom y
+ * coordinate (y2).  Thus all rectangles in a band differ only in their left
+ * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
+ * there is no separate list of band start pointers.
+ *
+ * The y-x band representation does not minimize rectangles.  In particular,
+ * if a rectangle vertically crosses a band (the rectangle has scanlines in
+ * the y1 to y2 area spanned by the band), then the rectangle may be broken
+ * down into two or more smaller rectangles stacked one atop the other.
+ *
+ *  -----------				    -----------
+ *  |         |				    |         |		    band 0
+ *  |         |  --------		    -----------  --------
+ *  |         |  |      |  in y-x banded    |         |  |      |   band 1
+ *  |         |  |      |  form is	    |         |  |      |
+ *  -----------  |      |		    -----------  --------
+ *               |      |				 |      |   band 2
+ *               --------				 --------
+ *
+ * An added constraint on the rectangles is that they must cover as much
+ * horizontal area as possible: no two rectangles within a band are allowed
+ * to touch.
+ *
+ * Whenever possible, bands will be merged together to cover a greater vertical
+ * distance (and thus reduce the number of rectangles). Two bands can be merged
+ * only if the bottom of one touches the top of the other and they have
+ * rectangles in the same places (of the same width, of course).
+ *
+ * Adam de Boor wrote most of the original region code.  Joel McCormack
+ * substantially modified or rewrote most of the core arithmetic routines, and
+ * added pixman_region_validate in order to support several speed improvements
+ * to pixman_region_validate_tree.  Bob Scheifler changed the representation
+ * to be more compact when empty or a single rectangle, and did a bunch of
+ * gratuitous reformatting. Carl Worth did further gratuitous reformatting
+ * while re-merging the server and client region code into libpixregion.
+ * Soren Sandmann did even more gratuitous reformatting.
+ */
+
+/*  true iff two Boxes overlap */
+#define EXTENTCHECK(r1, r2)	   \
+    (!( ((r1)->x2 <= (r2)->x1)  || \
+        ((r1)->x1 >= (r2)->x2)  || \
+        ((r1)->y2 <= (r2)->y1)  || \
+        ((r1)->y1 >= (r2)->y2) ) )
+
+/* true iff (x,y) is in Box */
+#define INBOX(r, x, y)	\
+    ( ((r)->x2 >  x) && \
+      ((r)->x1 <= x) && \
+      ((r)->y2 >  y) && \
+      ((r)->y1 <= y) )
+
+/* true iff Box r1 contains Box r2 */
+#define SUBSUMES(r1, r2)	\
+    ( ((r1)->x1 <= (r2)->x1) && \
+      ((r1)->x2 >= (r2)->x2) && \
+      ((r1)->y1 <= (r2)->y1) && \
+      ((r1)->y2 >= (r2)->y2) )
+
+static size_t
+PIXREGION_SZOF (size_t n)
+{
+    size_t size = n * sizeof(box_type_t);
+
+    if (n > UINT32_MAX / sizeof(box_type_t))
+    return 0;
+
+    if (sizeof(region_data_type_t) > UINT32_MAX - size)
+    return 0;
+
+    return size + sizeof(region_data_type_t);
+}
+
+static region_data_type_t *
+alloc_data (size_t n)
+{
+    size_t sz = PIXREGION_SZOF (n);
+
+    if (!sz)
+    return NULL;
+
+    return malloc (sz);
+}
+
+#define FREE_DATA(reg) if ((reg)->data && (reg)->data->size) free ((reg)->data)
+
+#define RECTALLOC_BAIL(region, n, bail)					\
+    do									\
+    {									\
+    if (!(region)->data ||						\
+        (((region)->data->numRects + (n)) > (region)->data->size))	\
+    {								\
+        if (!pixman_rect_alloc (region, n))				\
+        goto bail;						\
+    }								\
+    } while (0)
+
+#define RECTALLOC(region, n)						\
+    do									\
+    {									\
+    if (!(region)->data ||						\
+        (((region)->data->numRects + (n)) > (region)->data->size))	\
+    {								\
+        if (!pixman_rect_alloc (region, n)) {			\
+        return FALSE;						\
+        }								\
+    }								\
+    } while (0)
+
+#define ADDRECT(next_rect, nx1, ny1, nx2, ny2)      \
+    do						    \
+    {						    \
+    next_rect->x1 = nx1;                        \
+    next_rect->y1 = ny1;                        \
+    next_rect->x2 = nx2;                        \
+    next_rect->y2 = ny2;                        \
+    next_rect++;                                \
+    }						    \
+    while (0)
+
+#define NEWRECT(region, next_rect, nx1, ny1, nx2, ny2)			\
+    do									\
+    {									\
+    if (!(region)->data ||						\
+        ((region)->data->numRects == (region)->data->size))		\
+    {								\
+        if (!pixman_rect_alloc (region, 1))				\
+        return FALSE;						\
+        next_rect = PIXREGION_TOP (region);				\
+    }								\
+    ADDRECT (next_rect, nx1, ny1, nx2, ny2);			\
+    region->data->numRects++;					\
+    critical_if_fail (region->data->numRects <= region->data->size);		\
+    } while (0)
+
+#define DOWNSIZE(reg, numRects)						\
+    do									\
+    {									\
+    if (((numRects) < ((reg)->data->size >> 1)) &&			\
+        ((reg)->data->size > 50))					\
+    {								\
+        region_data_type_t * new_data;				\
+        size_t data_size = PIXREGION_SZOF (numRects);		\
+                                    \
+        if (!data_size)						\
+        {								\
+        new_data = NULL;					\
+        }								\
+        else							\
+        {								\
+        new_data = (region_data_type_t *)			\
+            realloc ((reg)->data, data_size);			\
+        }								\
+                                    \
+        if (new_data)						\
+        {								\
+        new_data->size = (numRects);				\
+        (reg)->data = new_data;					\
+        }								\
+    }								\
+    } while (0)
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_equal) (region_type_t *reg1, region_type_t *reg2)
+{
+    int i;
+    box_type_t *rects1;
+    box_type_t *rects2;
+
+    if (reg1->extents.x1 != reg2->extents.x1)
+    return FALSE;
+
+    if (reg1->extents.x2 != reg2->extents.x2)
+    return FALSE;
+
+    if (reg1->extents.y1 != reg2->extents.y1)
+    return FALSE;
+
+    if (reg1->extents.y2 != reg2->extents.y2)
+    return FALSE;
+
+    if (PIXREGION_NUMRECTS (reg1) != PIXREGION_NUMRECTS (reg2))
+    return FALSE;
+
+    rects1 = PIXREGION_RECTS (reg1);
+    rects2 = PIXREGION_RECTS (reg2);
+
+    for (i = 0; i != PIXREGION_NUMRECTS (reg1); i++)
+    {
+    if (rects1[i].x1 != rects2[i].x1)
+        return FALSE;
+
+    if (rects1[i].x2 != rects2[i].x2)
+        return FALSE;
+
+    if (rects1[i].y1 != rects2[i].y1)
+        return FALSE;
+
+    if (rects1[i].y2 != rects2[i].y2)
+        return FALSE;
+    }
+
+    return TRUE;
+}
+
+int
+PREFIX (_print) (region_type_t *rgn)
+{
+    int num, size;
+    int i;
+    box_type_t * rects;
+
+    num = PIXREGION_NUMRECTS (rgn);
+    size = PIXREGION_SIZE (rgn);
+    rects = PIXREGION_RECTS (rgn);
+
+    fprintf (stderr, "num: %d size: %d\n", num, size);
+    fprintf (stderr, "extents: %d %d %d %d\n",
+             rgn->extents.x1,
+         rgn->extents.y1,
+         rgn->extents.x2,
+         rgn->extents.y2);
+
+    for (i = 0; i < num; i++)
+    {
+    fprintf (stderr, "%d %d %d %d \n",
+             rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
+    }
+
+    fprintf (stderr, "\n");
+
+    return(num);
+}
+
+
+PIXMAN_EXPORT void
+PREFIX (_init) (region_type_t *region)
+{
+    region->extents = *pixman_region_empty_box;
+    region->data = pixman_region_empty_data;
+}
+
+PIXMAN_EXPORT void
+PREFIX (_init_rect) (region_type_t *	region,
+                     int		x,
+             int		y,
+             unsigned int	width,
+             unsigned int	height)
+{
+    region->extents.x1 = x;
+    region->extents.y1 = y;
+    region->extents.x2 = x + width;
+    region->extents.y2 = y + height;
+
+    if (!GOOD_RECT (&region->extents))
+    {
+        if (BAD_RECT (&region->extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+        PREFIX (_init) (region);
+        return;
+    }
+
+    region->data = NULL;
+}
+#if 0
+PIXMAN_EXPORT void
+PREFIX (_init_with_extents) (region_type_t *region, box_type_t *extents)
+{
+    if (!GOOD_RECT (extents))
+    {
+        if (BAD_RECT (extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+        PREFIX (_init) (region);
+        return;
+    }
+    region->extents = *extents;
+
+    region->data = NULL;
+}
+#endif
+PIXMAN_EXPORT void
+PREFIX (_fini) (region_type_t *region)
+{
+    GOOD (region);
+    FREE_DATA (region);
+}
+
+PIXMAN_EXPORT int
+PREFIX (_n_rects) (region_type_t *region)
+{
+    return PIXREGION_NUMRECTS (region);
+}
+#if 0
+PIXMAN_EXPORT box_type_t *
+PREFIX (_rectangles) (region_type_t *region,
+                      int               *n_rects)
+{
+    if (n_rects)
+    *n_rects = PIXREGION_NUMRECTS (region);
+
+    return PIXREGION_RECTS (region);
+}
+#endif
+static pixman_bool_t
+pixman_break (region_type_t *region)
+{
+    FREE_DATA (region);
+
+    region->extents = *pixman_region_empty_box;
+    region->data = pixman_broken_data;
+
+    return FALSE;
+}
+
+static pixman_bool_t
+pixman_rect_alloc (region_type_t * region,
+                   int             n)
+{
+    region_data_type_t *data;
+
+    if (!region->data)
+    {
+    n++;
+    region->data = alloc_data (n);
+
+    if (!region->data)
+        return pixman_break (region);
+
+    region->data->numRects = 1;
+    *PIXREGION_BOXPTR (region) = region->extents;
+    }
+    else if (!region->data->size)
+    {
+    region->data = alloc_data (n);
+
+    if (!region->data)
+        return pixman_break (region);
+
+    region->data->numRects = 0;
+    }
+    else
+    {
+    size_t data_size;
+
+    if (n == 1)
+    {
+        n = region->data->numRects;
+        if (n > 500) /* XXX pick numbers out of a hat */
+        n = 250;
+    }
+
+    n += region->data->numRects;
+    data_size = PIXREGION_SZOF (n);
+
+    if (!data_size)
+    {
+        data = NULL;
+    }
+    else
+    {
+        data = (region_data_type_t *)
+        realloc (region->data, PIXREGION_SZOF (n));
+    }
+
+    if (!data)
+        return pixman_break (region);
+
+    region->data = data;
+    }
+
+    region->data->size = n;
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_copy) (region_type_t *dst, region_type_t *src)
+{
+    GOOD (dst);
+    GOOD (src);
+
+    if (dst == src)
+    return TRUE;
+
+    dst->extents = src->extents;
+
+    if (!src->data || !src->data->size)
+    {
+    FREE_DATA (dst);
+    dst->data = src->data;
+    return TRUE;
+    }
+
+    if (!dst->data || (dst->data->size < src->data->numRects))
+    {
+    FREE_DATA (dst);
+
+    dst->data = alloc_data (src->data->numRects);
+
+    if (!dst->data)
+        return pixman_break (dst);
+
+    dst->data->size = src->data->numRects;
+    }
+
+    dst->data->numRects = src->data->numRects;
+
+    memmove ((char *)PIXREGION_BOXPTR (dst), (char *)PIXREGION_BOXPTR (src),
+             dst->data->numRects * sizeof(box_type_t));
+
+    return TRUE;
+}
+
+/*======================================================================
+ *	    Generic Region Operator
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_coalesce --
+ *	Attempt to merge the boxes in the current band with those in the
+ *	previous one.  We are guaranteed that the current band extends to
+ *      the end of the rects array.  Used only by pixman_op.
+ *
+ * Results:
+ *	The new index for the previous band.
+ *
+ * Side Effects:
+ *	If coalescing takes place:
+ *	    - rectangles in the previous band will have their y2 fields
+ *	      altered.
+ *	    - region->data->numRects will be decreased.
+ *
+ *-----------------------------------------------------------------------
+ */
+static inline int
+pixman_coalesce (region_type_t * region,      /* Region to coalesce		 */
+         int             prev_start,  /* Index of start of previous band */
+         int             cur_start)   /* Index of start of current band  */
+{
+    box_type_t *prev_box;       /* Current box in previous band	     */
+    box_type_t *cur_box;        /* Current box in current band       */
+    int numRects;               /* Number rectangles in both bands   */
+    int y2;                     /* Bottom of current band	     */
+
+    /*
+     * Figure out how many rectangles are in the band.
+     */
+    numRects = cur_start - prev_start;
+    critical_if_fail (numRects == region->data->numRects - cur_start);
+
+    if (!numRects) return cur_start;
+
+    /*
+     * The bands may only be coalesced if the bottom of the previous
+     * matches the top scanline of the current.
+     */
+    prev_box = PIXREGION_BOX (region, prev_start);
+    cur_box = PIXREGION_BOX (region, cur_start);
+    if (prev_box->y2 != cur_box->y1) return cur_start;
+
+    /*
+     * Make sure the bands have boxes in the same places. This
+     * assumes that boxes have been added in such a way that they
+     * cover the most area possible. I.e. two boxes in a band must
+     * have some horizontal space between them.
+     */
+    y2 = cur_box->y2;
+
+    do
+    {
+    if ((prev_box->x1 != cur_box->x1) || (prev_box->x2 != cur_box->x2))
+        return (cur_start);
+
+    prev_box++;
+    cur_box++;
+    numRects--;
+    }
+    while (numRects);
+
+    /*
+     * The bands may be merged, so set the bottom y of each box
+     * in the previous band to the bottom y of the current band.
+     */
+    numRects = cur_start - prev_start;
+    region->data->numRects -= numRects;
+
+    do
+    {
+    prev_box--;
+    prev_box->y2 = y2;
+    numRects--;
+    }
+    while (numRects);
+
+    return prev_start;
+}
+
+/* Quicky macro to avoid trivial reject procedure calls to pixman_coalesce */
+
+#define COALESCE(new_reg, prev_band, cur_band)                          \
+    do									\
+    {									\
+    if (cur_band - prev_band == new_reg->data->numRects - cur_band)	\
+        prev_band = pixman_coalesce (new_reg, prev_band, cur_band);	\
+    else								\
+        prev_band = cur_band;					\
+    } while (0)
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_append_non_o --
+ *	Handle a non-overlapping band for the union and subtract operations.
+ *      Just adds the (top/bottom-clipped) rectangles into the region.
+ *      Doesn't have to check for subsumption or anything.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	region->data->numRects is incremented and the rectangles overwritten
+ *	with the rectangles we're passed.
+ *
+ *-----------------------------------------------------------------------
+ */
+static inline pixman_bool_t
+pixman_region_append_non_o (region_type_t * region,
+                box_type_t *    r,
+                box_type_t *    r_end,
+                int             y1,
+                int             y2)
+{
+    box_type_t *next_rect;
+    int new_rects;
+
+    new_rects = r_end - r;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (new_rects != 0);
+
+    /* Make sure we have enough space for all rectangles to be added */
+    RECTALLOC (region, new_rects);
+    next_rect = PIXREGION_TOP (region);
+    region->data->numRects += new_rects;
+
+    do
+    {
+    critical_if_fail (r->x1 < r->x2);
+    ADDRECT (next_rect, r->x1, y1, r->x2, y2);
+    r++;
+    }
+    while (r != r_end);
+
+    return TRUE;
+}
+
+#define FIND_BAND(r, r_band_end, r_end, ry1)			     \
+    do								     \
+    {								     \
+    ry1 = r->y1;						     \
+    r_band_end = r + 1;					     \
+    while ((r_band_end != r_end) && (r_band_end->y1 == ry1)) {   \
+        r_band_end++;					     \
+    }							     \
+    } while (0)
+
+#define APPEND_REGIONS(new_reg, r, r_end)				\
+    do									\
+    {									\
+    int new_rects;							\
+    if ((new_rects = r_end - r)) {					\
+        RECTALLOC_BAIL (new_reg, new_rects, bail);			\
+        memmove ((char *)PIXREGION_TOP (new_reg), (char *)r,	\
+             new_rects * sizeof(box_type_t));			\
+        new_reg->data->numRects += new_rects;			\
+    }								\
+    } while (0)
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_op --
+ *	Apply an operation to two regions. Called by pixman_region_union, pixman_region_inverse,
+ *	pixman_region_subtract, pixman_region_intersect....  Both regions MUST have at least one
+ *      rectangle, and cannot be the same object.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	The new region is overwritten.
+ *	overlap set to TRUE if overlap_func ever returns TRUE.
+ *
+ * Notes:
+ *	The idea behind this function is to view the two regions as sets.
+ *	Together they cover a rectangle of area that this function divides
+ *	into horizontal bands where points are covered only by one region
+ *	or by both. For the first case, the non_overlap_func is called with
+ *	each the band and the band's upper and lower extents. For the
+ *	second, the overlap_func is called to process the entire band. It
+ *	is responsible for clipping the rectangles in the band, though
+ *	this function provides the boundaries.
+ *	At the end of each band, the new region is coalesced, if possible,
+ *	to reduce the number of rectangles in the region.
+ *
+ *-----------------------------------------------------------------------
+ */
+
+typedef pixman_bool_t (*overlap_proc_ptr) (region_type_t *region,
+                       box_type_t *   r1,
+                       box_type_t *   r1_end,
+                       box_type_t *   r2,
+                       box_type_t *   r2_end,
+                       int            y1,
+                       int            y2);
+
+static pixman_bool_t
+pixman_op (region_type_t *  new_reg,               /* Place to store result	    */
+       region_type_t *  reg1,                  /* First region in operation     */
+       region_type_t *  reg2,                  /* 2d region in operation        */
+       overlap_proc_ptr overlap_func,          /* Function to call for over-
+                            * lapping bands		    */
+       int              append_non1,           /* Append non-overlapping bands
+                            * in region 1 ?
+                            */
+       int              append_non2            /* Append non-overlapping bands
+                            * in region 2 ?
+                            */
+    )
+{
+    box_type_t *r1;                 /* Pointer into first region     */
+    box_type_t *r2;                 /* Pointer into 2d region	     */
+    box_type_t *r1_end;             /* End of 1st region	     */
+    box_type_t *r2_end;             /* End of 2d region		     */
+    int ybot;                       /* Bottom of intersection	     */
+    int ytop;                       /* Top of intersection	     */
+    region_data_type_t *old_data;   /* Old data for new_reg	     */
+    int prev_band;                  /* Index of start of
+                     * previous band in new_reg       */
+    int cur_band;                   /* Index of start of current
+                     * band in new_reg		     */
+    box_type_t * r1_band_end;       /* End of current band in r1     */
+    box_type_t * r2_band_end;       /* End of current band in r2     */
+    int top;                        /* Top of non-overlapping band   */
+    int bot;                        /* Bottom of non-overlapping band*/
+    int r1y1;                       /* Temps for r1->y1 and r2->y1   */
+    int r2y1;
+    int new_size;
+    int numRects;
+
+    /*
+     * Break any region computed from a broken region
+     */
+    if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
+    return pixman_break (new_reg);
+
+    /*
+     * Initialization:
+     *	set r1, r2, r1_end and r2_end appropriately, save the rectangles
+     * of the destination region until the end in case it's one of
+     * the two source regions, then mark the "new" region empty, allocating
+     * another array of rectangles for it to use.
+     */
+
+    r1 = PIXREGION_RECTS (reg1);
+    new_size = PIXREGION_NUMRECTS (reg1);
+    r1_end = r1 + new_size;
+
+    numRects = PIXREGION_NUMRECTS (reg2);
+    r2 = PIXREGION_RECTS (reg2);
+    r2_end = r2 + numRects;
+
+    critical_if_fail (r1 != r1_end);
+    critical_if_fail (r2 != r2_end);
+
+    old_data = (region_data_type_t *)NULL;
+
+    if (((new_reg == reg1) && (new_size > 1)) ||
+        ((new_reg == reg2) && (numRects > 1)))
+    {
+        old_data = new_reg->data;
+        new_reg->data = pixman_region_empty_data;
+    }
+
+    /* guess at new size */
+    if (numRects > new_size)
+    new_size = numRects;
+
+    new_size <<= 1;
+
+    if (!new_reg->data)
+    new_reg->data = pixman_region_empty_data;
+    else if (new_reg->data->size)
+    new_reg->data->numRects = 0;
+
+    if (new_size > new_reg->data->size)
+    {
+        if (!pixman_rect_alloc (new_reg, new_size))
+        {
+            free (old_data);
+            return FALSE;
+    }
+    }
+
+    /*
+     * Initialize ybot.
+     * In the upcoming loop, ybot and ytop serve different functions depending
+     * on whether the band being handled is an overlapping or non-overlapping
+     * band.
+     *  In the case of a non-overlapping band (only one of the regions
+     * has points in the band), ybot is the bottom of the most recent
+     * intersection and thus clips the top of the rectangles in that band.
+     * ytop is the top of the next intersection between the two regions and
+     * serves to clip the bottom of the rectangles in the current band.
+     *	For an overlapping band (where the two regions intersect), ytop clips
+     * the top of the rectangles of both regions and ybot clips the bottoms.
+     */
+
+    ybot = MIN (r1->y1, r2->y1);
+
+    /*
+     * prev_band serves to mark the start of the previous band so rectangles
+     * can be coalesced into larger rectangles. qv. pixman_coalesce, above.
+     * In the beginning, there is no previous band, so prev_band == cur_band
+     * (cur_band is set later on, of course, but the first band will always
+     * start at index 0). prev_band and cur_band must be indices because of
+     * the possible expansion, and resultant moving, of the new region's
+     * array of rectangles.
+     */
+    prev_band = 0;
+
+    do
+    {
+        /*
+     * This algorithm proceeds one source-band (as opposed to a
+     * destination band, which is determined by where the two regions
+     * intersect) at a time. r1_band_end and r2_band_end serve to mark the
+     * rectangle after the last one in the current band for their
+     * respective regions.
+     */
+        critical_if_fail (r1 != r1_end);
+        critical_if_fail (r2 != r2_end);
+
+        FIND_BAND (r1, r1_band_end, r1_end, r1y1);
+        FIND_BAND (r2, r2_band_end, r2_end, r2y1);
+
+        /*
+     * First handle the band that doesn't intersect, if any.
+     *
+     * Note that attention is restricted to one band in the
+     * non-intersecting region at once, so if a region has n
+     * bands between the current position and the next place it overlaps
+     * the other, this entire loop will be passed through n times.
+     */
+        if (r1y1 < r2y1)
+        {
+            if (append_non1)
+            {
+                top = MAX (r1y1, ybot);
+                bot = MIN (r1->y2, r2y1);
+                if (top != bot)
+                {
+                    cur_band = new_reg->data->numRects;
+                    if (!pixman_region_append_non_o (new_reg, r1, r1_band_end, top, bot))
+            goto bail;
+                    COALESCE (new_reg, prev_band, cur_band);
+        }
+        }
+            ytop = r2y1;
+    }
+        else if (r2y1 < r1y1)
+        {
+            if (append_non2)
+            {
+                top = MAX (r2y1, ybot);
+                bot = MIN (r2->y2, r1y1);
+
+                if (top != bot)
+                {
+                    cur_band = new_reg->data->numRects;
+
+                    if (!pixman_region_append_non_o (new_reg, r2, r2_band_end, top, bot))
+            goto bail;
+
+                    COALESCE (new_reg, prev_band, cur_band);
+        }
+        }
+            ytop = r1y1;
+    }
+        else
+        {
+            ytop = r1y1;
+    }
+
+        /*
+     * Now see if we've hit an intersecting band. The two bands only
+     * intersect if ybot > ytop
+     */
+        ybot = MIN (r1->y2, r2->y2);
+        if (ybot > ytop)
+        {
+            cur_band = new_reg->data->numRects;
+
+            if (!(*overlap_func)(new_reg,
+                                 r1, r1_band_end,
+                                 r2, r2_band_end,
+                                 ytop, ybot))
+        {
+        goto bail;
+        }
+
+            COALESCE (new_reg, prev_band, cur_band);
+    }
+
+        /*
+     * If we've finished with a band (y2 == ybot) we skip forward
+     * in the region to the next band.
+     */
+        if (r1->y2 == ybot)
+        r1 = r1_band_end;
+
+        if (r2->y2 == ybot)
+        r2 = r2_band_end;
+
+    }
+    while (r1 != r1_end && r2 != r2_end);
+
+    /*
+     * Deal with whichever region (if any) still has rectangles left.
+     *
+     * We only need to worry about banding and coalescing for the very first
+     * band left.  After that, we can just group all remaining boxes,
+     * regardless of how many bands, into one final append to the list.
+     */
+
+    if ((r1 != r1_end) && append_non1)
+    {
+        /* Do first non_overlap1Func call, which may be able to coalesce */
+        FIND_BAND (r1, r1_band_end, r1_end, r1y1);
+
+        cur_band = new_reg->data->numRects;
+
+        if (!pixman_region_append_non_o (new_reg,
+                                         r1, r1_band_end,
+                                         MAX (r1y1, ybot), r1->y2))
+    {
+        goto bail;
+    }
+
+        COALESCE (new_reg, prev_band, cur_band);
+
+        /* Just append the rest of the boxes  */
+        APPEND_REGIONS (new_reg, r1_band_end, r1_end);
+    }
+    else if ((r2 != r2_end) && append_non2)
+    {
+        /* Do first non_overlap2Func call, which may be able to coalesce */
+        FIND_BAND (r2, r2_band_end, r2_end, r2y1);
+
+    cur_band = new_reg->data->numRects;
+
+        if (!pixman_region_append_non_o (new_reg,
+                                         r2, r2_band_end,
+                                         MAX (r2y1, ybot), r2->y2))
+    {
+        goto bail;
+    }
+
+        COALESCE (new_reg, prev_band, cur_band);
+
+        /* Append rest of boxes */
+        APPEND_REGIONS (new_reg, r2_band_end, r2_end);
+    }
+
+    free (old_data);
+
+    if (!(numRects = new_reg->data->numRects))
+    {
+        FREE_DATA (new_reg);
+        new_reg->data = pixman_region_empty_data;
+    }
+    else if (numRects == 1)
+    {
+        new_reg->extents = *PIXREGION_BOXPTR (new_reg);
+        FREE_DATA (new_reg);
+        new_reg->data = (region_data_type_t *)NULL;
+    }
+    else
+    {
+        DOWNSIZE (new_reg, numRects);
+    }
+
+    return TRUE;
+
+bail:
+    free (old_data);
+
+    return pixman_break (new_reg);
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_set_extents --
+ *	Reset the extents of a region to what they should be. Called by
+ *	pixman_region_subtract and pixman_region_intersect as they can't
+ *      figure it out along the way or do so easily, as pixman_region_union can.
+ *
+ * Results:
+ *	None.
+ *
+ * Side Effects:
+ *	The region's 'extents' structure is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+static void
+pixman_set_extents (region_type_t *region)
+{
+    box_type_t *box, *box_end;
+
+    if (!region->data)
+    return;
+
+    if (!region->data->size)
+    {
+        region->extents.x2 = region->extents.x1;
+        region->extents.y2 = region->extents.y1;
+        return;
+    }
+
+    box = PIXREGION_BOXPTR (region);
+    box_end = PIXREGION_END (region);
+
+    /*
+     * Since box is the first rectangle in the region, it must have the
+     * smallest y1 and since box_end is the last rectangle in the region,
+     * it must have the largest y2, because of banding. Initialize x1 and
+     * x2 from  box and box_end, resp., as good things to initialize them
+     * to...
+     */
+    region->extents.x1 = box->x1;
+    region->extents.y1 = box->y1;
+    region->extents.x2 = box_end->x2;
+    region->extents.y2 = box_end->y2;
+
+    critical_if_fail (region->extents.y1 < region->extents.y2);
+
+    while (box <= box_end)
+    {
+        if (box->x1 < region->extents.x1)
+        region->extents.x1 = box->x1;
+        if (box->x2 > region->extents.x2)
+        region->extents.x2 = box->x2;
+        box++;
+    }
+
+    critical_if_fail (region->extents.x1 < region->extents.x2);
+}
+
+/*======================================================================
+ *	    Region Intersection
+ *====================================================================*/
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_intersect_o --
+ *	Handle an overlapping band for pixman_region_intersect.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	Rectangles may be added to the region.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*ARGSUSED*/
+static pixman_bool_t
+pixman_region_intersect_o (region_type_t *region,
+                           box_type_t *   r1,
+                           box_type_t *   r1_end,
+                           box_type_t *   r2,
+                           box_type_t *   r2_end,
+                           int            y1,
+                           int            y2)
+{
+    int x1;
+    int x2;
+    box_type_t *        next_rect;
+
+    next_rect = PIXREGION_TOP (region);
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    do
+    {
+        x1 = MAX (r1->x1, r2->x1);
+        x2 = MIN (r1->x2, r2->x2);
+
+        /*
+     * If there's any overlap between the two rectangles, add that
+     * overlap to the new region.
+     */
+        if (x1 < x2)
+        NEWRECT (region, next_rect, x1, y1, x2, y2);
+
+        /*
+     * Advance the pointer(s) with the leftmost right side, since the next
+     * rectangle on that list may still overlap the other region's
+     * current rectangle.
+     */
+        if (r1->x2 == x2)
+        {
+            r1++;
+    }
+        if (r2->x2 == x2)
+        {
+            r2++;
+    }
+    }
+    while ((r1 != r1_end) && (r2 != r2_end));
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_intersect) (region_type_t *     new_reg,
+                     region_type_t *        reg1,
+                     region_type_t *        reg2)
+{
+    GOOD (reg1);
+    GOOD (reg2);
+    GOOD (new_reg);
+
+    /* check for trivial reject */
+    if (PIXREGION_NIL (reg1) || PIXREGION_NIL (reg2) ||
+        !EXTENTCHECK (&reg1->extents, &reg2->extents))
+    {
+        /* Covers about 20% of all cases */
+        FREE_DATA (new_reg);
+        new_reg->extents.x2 = new_reg->extents.x1;
+        new_reg->extents.y2 = new_reg->extents.y1;
+        if (PIXREGION_NAR (reg1) || PIXREGION_NAR (reg2))
+        {
+            new_reg->data = pixman_broken_data;
+            return FALSE;
+    }
+        else
+    {
+        new_reg->data = pixman_region_empty_data;
+    }
+    }
+    else if (!reg1->data && !reg2->data)
+    {
+        /* Covers about 80% of cases that aren't trivially rejected */
+        new_reg->extents.x1 = MAX (reg1->extents.x1, reg2->extents.x1);
+        new_reg->extents.y1 = MAX (reg1->extents.y1, reg2->extents.y1);
+        new_reg->extents.x2 = MIN (reg1->extents.x2, reg2->extents.x2);
+        new_reg->extents.y2 = MIN (reg1->extents.y2, reg2->extents.y2);
+
+        FREE_DATA (new_reg);
+
+    new_reg->data = (region_data_type_t *)NULL;
+    }
+    else if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
+    {
+        return PREFIX (_copy) (new_reg, reg1);
+    }
+    else if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
+    {
+        return PREFIX (_copy) (new_reg, reg2);
+    }
+    else if (reg1 == reg2)
+    {
+        return PREFIX (_copy) (new_reg, reg1);
+    }
+    else
+    {
+        /* General purpose intersection */
+
+        if (!pixman_op (new_reg, reg1, reg2, pixman_region_intersect_o, FALSE, FALSE))
+        return FALSE;
+
+        pixman_set_extents (new_reg);
+    }
+
+    GOOD (new_reg);
+    return(TRUE);
+}
+
+#define MERGERECT(r)							\
+    do									\
+    {									\
+        if (r->x1 <= x2)						\
+    {								\
+            /* Merge with current rectangle */				\
+            if (x2 < r->x2)						\
+        x2 = r->x2;						\
+    }								\
+    else								\
+    {								\
+            /* Add current rectangle, start new one */			\
+            NEWRECT (region, next_rect, x1, y1, x2, y2);		\
+            x1 = r->x1;							\
+            x2 = r->x2;							\
+    }								\
+        r++;								\
+    } while (0)
+
+/*======================================================================
+ *	    Region Union
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_union_o --
+ *	Handle an overlapping band for the union operation. Picks the
+ *	left-most rectangle each time and merges it into the region.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	region is overwritten.
+ *	overlap is set to TRUE if any boxes overlap.
+ *
+ *-----------------------------------------------------------------------
+ */
+static pixman_bool_t
+pixman_region_union_o (region_type_t *region,
+               box_type_t *   r1,
+               box_type_t *   r1_end,
+               box_type_t *   r2,
+               box_type_t *   r2_end,
+               int            y1,
+               int            y2)
+{
+    box_type_t *next_rect;
+    int x1;            /* left and right side of current union */
+    int x2;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    next_rect = PIXREGION_TOP (region);
+
+    /* Start off current rectangle */
+    if (r1->x1 < r2->x1)
+    {
+        x1 = r1->x1;
+        x2 = r1->x2;
+        r1++;
+    }
+    else
+    {
+        x1 = r2->x1;
+        x2 = r2->x2;
+        r2++;
+    }
+    while (r1 != r1_end && r2 != r2_end)
+    {
+        if (r1->x1 < r2->x1)
+        MERGERECT (r1);
+    else
+        MERGERECT (r2);
+    }
+
+    /* Finish off whoever (if any) is left */
+    if (r1 != r1_end)
+    {
+        do
+        {
+            MERGERECT (r1);
+    }
+        while (r1 != r1_end);
+    }
+    else if (r2 != r2_end)
+    {
+        do
+        {
+            MERGERECT (r2);
+    }
+        while (r2 != r2_end);
+    }
+
+    /* Add current rectangle */
+    NEWRECT (region, next_rect, x1, y1, x2, y2);
+
+    return TRUE;
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX(_intersect_rect) (region_type_t *dest,
+             region_type_t *source,
+             int x, int y,
+             unsigned int width,
+             unsigned int height)
+{
+    region_type_t region;
+
+    region.data = NULL;
+    region.extents.x1 = x;
+    region.extents.y1 = y;
+    region.extents.x2 = x + width;
+    region.extents.y2 = y + height;
+
+    return PREFIX(_intersect) (dest, source, &region);
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_union) (region_type_t *new_reg,
+                 region_type_t *reg1,
+                 region_type_t *reg2);
+
+/* Convenience function for performing union of region with a
+ * single rectangle
+ */
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_union_rect) (region_type_t *dest,
+                      region_type_t *source,
+                      int            x,
+              int            y,
+                      unsigned int   width,
+              unsigned int   height)
+{
+    region_type_t region;
+
+    region.extents.x1 = x;
+    region.extents.y1 = y;
+    region.extents.x2 = x + width;
+    region.extents.y2 = y + height;
+
+    if (!GOOD_RECT (&region.extents))
+    {
+        if (BAD_RECT (&region.extents))
+            _pixman_log_error (FUNC, "Invalid rectangle passed");
+    return PREFIX (_copy) (dest, source);
+    }
+
+    region.data = NULL;
+
+    return PREFIX (_union) (dest, source, &region);
+}
+
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_union) (region_type_t *new_reg,
+                 region_type_t *reg1,
+                 region_type_t *reg2)
+{
+    /* Return TRUE if some overlap
+     * between reg1, reg2
+     */
+    GOOD (reg1);
+    GOOD (reg2);
+    GOOD (new_reg);
+
+    /*  checks all the simple cases */
+
+    /*
+     * Region 1 and 2 are the same
+     */
+    if (reg1 == reg2)
+        return PREFIX (_copy) (new_reg, reg1);
+
+    /*
+     * Region 1 is empty
+     */
+    if (PIXREGION_NIL (reg1))
+    {
+        if (PIXREGION_NAR (reg1))
+        return pixman_break (new_reg);
+
+        if (new_reg != reg2)
+        return PREFIX (_copy) (new_reg, reg2);
+
+    return TRUE;
+    }
+
+    /*
+     * Region 2 is empty
+     */
+    if (PIXREGION_NIL (reg2))
+    {
+        if (PIXREGION_NAR (reg2))
+        return pixman_break (new_reg);
+
+    if (new_reg != reg1)
+        return PREFIX (_copy) (new_reg, reg1);
+
+    return TRUE;
+    }
+
+    /*
+     * Region 1 completely subsumes region 2
+     */
+    if (!reg1->data && SUBSUMES (&reg1->extents, &reg2->extents))
+    {
+        if (new_reg != reg1)
+        return PREFIX (_copy) (new_reg, reg1);
+
+    return TRUE;
+    }
+
+    /*
+     * Region 2 completely subsumes region 1
+     */
+    if (!reg2->data && SUBSUMES (&reg2->extents, &reg1->extents))
+    {
+        if (new_reg != reg2)
+        return PREFIX (_copy) (new_reg, reg2);
+
+    return TRUE;
+    }
+
+    if (!pixman_op (new_reg, reg1, reg2, pixman_region_union_o, TRUE, TRUE))
+    return FALSE;
+
+    new_reg->extents.x1 = MIN (reg1->extents.x1, reg2->extents.x1);
+    new_reg->extents.y1 = MIN (reg1->extents.y1, reg2->extents.y1);
+    new_reg->extents.x2 = MAX (reg1->extents.x2, reg2->extents.x2);
+    new_reg->extents.y2 = MAX (reg1->extents.y2, reg2->extents.y2);
+
+    GOOD (new_reg);
+
+    return TRUE;
+}
+
+/*======================================================================
+ *                Region Subtraction
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_subtract_o --
+ *	Overlapping band subtraction. x1 is the left-most point not yet
+ *	checked.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	region may have rectangles added to it.
+ *
+ *-----------------------------------------------------------------------
+ */
+/*ARGSUSED*/
+static pixman_bool_t
+pixman_region_subtract_o (region_type_t * region,
+              box_type_t *    r1,
+              box_type_t *    r1_end,
+              box_type_t *    r2,
+              box_type_t *    r2_end,
+              int             y1,
+              int             y2)
+{
+    box_type_t *        next_rect;
+    int x1;
+
+    x1 = r1->x1;
+
+    critical_if_fail (y1 < y2);
+    critical_if_fail (r1 != r1_end && r2 != r2_end);
+
+    next_rect = PIXREGION_TOP (region);
+
+    do
+    {
+        if (r2->x2 <= x1)
+        {
+            /*
+         * Subtrahend entirely to left of minuend: go to next subtrahend.
+         */
+            r2++;
+    }
+        else if (r2->x1 <= x1)
+        {
+            /*
+         * Subtrahend precedes minuend: nuke left edge of minuend.
+         */
+            x1 = r2->x2;
+            if (x1 >= r1->x2)
+            {
+                /*
+         * Minuend completely covered: advance to next minuend and
+         * reset left fence to edge of new minuend.
+         */
+                r1++;
+                if (r1 != r1_end)
+            x1 = r1->x1;
+        }
+            else
+            {
+                /*
+         * Subtrahend now used up since it doesn't extend beyond
+         * minuend
+         */
+                r2++;
+        }
+    }
+        else if (r2->x1 < r1->x2)
+        {
+            /*
+         * Left part of subtrahend covers part of minuend: add uncovered
+         * part of minuend to region and skip to next subtrahend.
+         */
+            critical_if_fail (x1 < r2->x1);
+            NEWRECT (region, next_rect, x1, y1, r2->x1, y2);
+
+            x1 = r2->x2;
+            if (x1 >= r1->x2)
+            {
+                /*
+         * Minuend used up: advance to new...
+         */
+                r1++;
+                if (r1 != r1_end)
+            x1 = r1->x1;
+        }
+            else
+            {
+                /*
+         * Subtrahend used up
+         */
+                r2++;
+        }
+    }
+        else
+        {
+            /*
+         * Minuend used up: add any remaining piece before advancing.
+         */
+            if (r1->x2 > x1)
+        NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
+
+            r1++;
+
+        if (r1 != r1_end)
+        x1 = r1->x1;
+    }
+    }
+    while ((r1 != r1_end) && (r2 != r2_end));
+
+    /*
+     * Add remaining minuend rectangles to region.
+     */
+    while (r1 != r1_end)
+    {
+        critical_if_fail (x1 < r1->x2);
+
+        NEWRECT (region, next_rect, x1, y1, r1->x2, y2);
+
+        r1++;
+        if (r1 != r1_end)
+        x1 = r1->x1;
+    }
+    return TRUE;
+}
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_subtract --
+ *	Subtract reg_s from reg_m and leave the result in reg_d.
+ *	S stands for subtrahend, M for minuend and D for difference.
+ *
+ * Results:
+ *	TRUE if successful.
+ *
+ * Side Effects:
+ *	reg_d is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_subtract) (region_type_t *reg_d,
+                    region_type_t *reg_m,
+                    region_type_t *reg_s)
+{
+    GOOD (reg_m);
+    GOOD (reg_s);
+    GOOD (reg_d);
+
+    /* check for trivial rejects */
+    if (PIXREGION_NIL (reg_m) || PIXREGION_NIL (reg_s) ||
+        !EXTENTCHECK (&reg_m->extents, &reg_s->extents))
+    {
+        if (PIXREGION_NAR (reg_s))
+        return pixman_break (reg_d);
+
+        return PREFIX (_copy) (reg_d, reg_m);
+    }
+    else if (reg_m == reg_s)
+    {
+        FREE_DATA (reg_d);
+        reg_d->extents.x2 = reg_d->extents.x1;
+        reg_d->extents.y2 = reg_d->extents.y1;
+        reg_d->data = pixman_region_empty_data;
+
+        return TRUE;
+    }
+
+    /* Add those rectangles in region 1 that aren't in region 2,
+       do yucky subtraction for overlaps, and
+       just throw away rectangles in region 2 that aren't in region 1 */
+    if (!pixman_op (reg_d, reg_m, reg_s, pixman_region_subtract_o, TRUE, FALSE))
+    return FALSE;
+
+    /*
+     * Can't alter reg_d's extents before we call pixman_op because
+     * it might be one of the source regions and pixman_op depends
+     * on the extents of those regions being unaltered. Besides, this
+     * way there's no checking against rectangles that will be nuked
+     * due to coalescing, so we have to examine fewer rectangles.
+     */
+    pixman_set_extents (reg_d);
+    GOOD (reg_d);
+    return TRUE;
+}
+#if 0
+/*======================================================================
+ *	    Region Inversion
+ *====================================================================*/
+
+/*-
+ *-----------------------------------------------------------------------
+ * pixman_region_inverse --
+ *	Take a region and a box and return a region that is everything
+ *	in the box but not in the region. The careful reader will note
+ *	that this is the same as subtracting the region from the box...
+ *
+ * Results:
+ *	TRUE.
+ *
+ * Side Effects:
+ *	new_reg is overwritten.
+ *
+ *-----------------------------------------------------------------------
+ */
+PIXMAN_EXPORT pixman_bool_t
+PREFIX (_inverse) (region_type_t *new_reg,  /* Destination region */
+           region_type_t *reg1,     /* Region to invert */
+           box_type_t *   inv_rect) /* Bounding box for inversion */
+{
+    region_type_t inv_reg; /* Quick and dirty region made from the
+                * bounding box */
+    GOOD (reg1);
+    GOOD (new_reg);
+
+    /* check for trivial rejects */
+    if (PIXREGION_NIL (reg1) || !EXTENTCHECK (inv_rect, &reg1->extents))
+    {
+        if (PIXREGION_NAR (reg1))
+        return pixman_break (new_reg);
+
+        new_reg->extents = *inv_rect;
+        FREE_DATA (new_reg);
+        new_reg->data = (region_data_type_t *)NULL;
+
+        return TRUE;
+    }
+
+    /* Add those rectangles in region 1 that aren't in region 2,
+     * do yucky subtraction for overlaps, and
+     * just throw away rectangles in region 2 that aren't in region 1
+     */
+    inv_reg.extents = *inv_rect;
+    inv_reg.data = (region_data_type_t *)NULL;
+    if (!pixman_op (new_reg, &inv_reg, reg1, pixman_region_subtract_o, TRUE, FALSE))
+    return FALSE;
+
+    /*
+     * Can't alter new_reg's extents before we call pixman_op because
+     * it might be one of the source regions and pixman_op depends
+     * on the extents of those regions being unaltered. Besides, this
+     * way there's no checking against rectangles that will be nuked
+     * due to coalescing, so we have to examine fewer rectangles.
+     */
+    pixman_set_extents (new_reg);
+    GOOD (new_reg);
+    return TRUE;
+}
+#endif
+/* In time O(log n), locate the first box whose y2 is greater than y.
+ * Return @end if no such box exists.
+ */
+static box_type_t *
+find_box_for_y (box_type_t *begin, box_type_t *end, int y)
+{
+    box_type_t *mid;
+
+    if (end == begin)
+    return end;
+
+    if (end - begin == 1)
+    {
+    if (begin->y2 > y)
+        return begin;
+    else
+        return end;
+    }
+
+    mid = begin + (end - begin) / 2;
+    if (mid->y2 > y)
+    {
+    /* If no box is found in [begin, mid], the function
+     * will return @mid, which is then known to be the
+     * correct answer.
+     */
+    return find_box_for_y (begin, mid, y);
+    }
+    else
+    {
+    return find_box_for_y (mid, end, y);
+    }
+}
+
+/*
+ *   rect_in(region, rect)
+ *   This routine takes a pointer to a region and a pointer to a box
+ *   and determines if the box is outside/inside/partly inside the region.
+ *
+ *   The idea is to travel through the list of rectangles trying to cover the
+ *   passed box with them. Anytime a piece of the rectangle isn't covered
+ *   by a band of rectangles, part_out is set TRUE. Any time a rectangle in
+ *   the region covers part of the box, part_in is set TRUE. The process ends
+ *   when either the box has been completely covered (we reached a band that
+ *   doesn't overlap the box, part_in is TRUE and part_out is false), the
+ *   box has been partially covered (part_in == part_out == TRUE -- because of
+ *   the banding, the first time this is true we know the box is only
+ *   partially in the region) or is outside the region (we reached a band
+ *   that doesn't overlap the box at all and part_in is false)
+ */
+PIXMAN_EXPORT pixman_region_overlap_t
+PREFIX (_contains_rectangle) (region_type_t *  region,
+                  box_type_t *     prect)
+{
+    box_type_t *     pbox;
+    box_type_t *     pbox_end;
+    int part_in, part_out;
+    int numRects;
+    int x, y;
+
+    GOOD (region);
+
+    numRects = PIXREGION_NUMRECTS (region);
+
+    /* useful optimization */
+    if (!numRects || !EXTENTCHECK (&region->extents, prect))
+    return(PIXMAN_REGION_OUT);
+
+    if (numRects == 1)
+    {
+        /* We know that it must be PIXMAN_REGION_IN or PIXMAN_REGION_PART */
+        if (SUBSUMES (&region->extents, prect))
+        return(PIXMAN_REGION_IN);
+        else
+        return(PIXMAN_REGION_PART);
+    }
+
+    part_out = FALSE;
+    part_in = FALSE;
+
+    /* (x,y) starts at upper left of rect, moving to the right and down */
+    x = prect->x1;
+    y = prect->y1;
+
+    /* can stop when both part_out and part_in are TRUE, or we reach prect->y2 */
+    for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects;
+     pbox != pbox_end;
+     pbox++)
+    {
+    /* getting up to speed or skipping remainder of band */
+    if (pbox->y2 <= y)
+    {
+        if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
+        break;
+    }
+
+        if (pbox->y1 > y)
+        {
+            part_out = TRUE;     /* missed part of rectangle above */
+            if (part_in || (pbox->y1 >= prect->y2))
+        break;
+            y = pbox->y1;       /* x guaranteed to be == prect->x1 */
+    }
+
+        if (pbox->x2 <= x)
+        continue;           /* not far enough over yet */
+
+        if (pbox->x1 > x)
+        {
+            part_out = TRUE;     /* missed part of rectangle to left */
+            if (part_in)
+        break;
+    }
+
+        if (pbox->x1 < prect->x2)
+        {
+            part_in = TRUE;      /* definitely overlap */
+            if (part_out)
+        break;
+    }
+
+        if (pbox->x2 >= prect->x2)
+        {
+            y = pbox->y2;       /* finished with this band */
+            if (y >= prect->y2)
+        break;
+            x = prect->x1;      /* reset x out to left again */
+    }
+        else
+        {
+            /*
+         * Because boxes in a band are maximal width, if the first box
+         * to overlap the rectangle doesn't completely cover it in that
+         * band, the rectangle must be partially out, since some of it
+         * will be uncovered in that band. part_in will have been set true
+         * by now...
+         */
+            part_out = TRUE;
+            break;
+    }
+    }
+
+    if (part_in)
+    {
+        if (y < prect->y2)
+        return PIXMAN_REGION_PART;
+        else
+        return PIXMAN_REGION_IN;
+    }
+    else
+    {
+        return PIXMAN_REGION_OUT;
+    }
+}
+
+/* PREFIX(_translate) (region, x, y)
+ * translates in place
+ */
+
+PIXMAN_EXPORT void
+PREFIX (_translate) (region_type_t *region, int x, int y)
+{
+    overflow_int_t x1, x2, y1, y2;
+    int nbox;
+    box_type_t * pbox;
+
+    GOOD (region);
+    region->extents.x1 = x1 = region->extents.x1 + x;
+    region->extents.y1 = y1 = region->extents.y1 + y;
+    region->extents.x2 = x2 = region->extents.x2 + x;
+    region->extents.y2 = y2 = region->extents.y2 + y;
+
+    if (((x1 - PIXMAN_REGION_MIN) | (y1 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x2) | (PIXMAN_REGION_MAX - y2)) >= 0)
+    {
+        if (region->data && (nbox = region->data->numRects))
+        {
+            for (pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
+            {
+                pbox->x1 += x;
+                pbox->y1 += y;
+                pbox->x2 += x;
+                pbox->y2 += y;
+        }
+    }
+        return;
+    }
+
+    if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) | (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
+    {
+        region->extents.x2 = region->extents.x1;
+        region->extents.y2 = region->extents.y1;
+        FREE_DATA (region);
+        region->data = pixman_region_empty_data;
+        return;
+    }
+
+    if (x1 < PIXMAN_REGION_MIN)
+    region->extents.x1 = PIXMAN_REGION_MIN;
+    else if (x2 > PIXMAN_REGION_MAX)
+    region->extents.x2 = PIXMAN_REGION_MAX;
+
+    if (y1 < PIXMAN_REGION_MIN)
+    region->extents.y1 = PIXMAN_REGION_MIN;
+    else if (y2 > PIXMAN_REGION_MAX)
+    region->extents.y2 = PIXMAN_REGION_MAX;
+
+    if (region->data && (nbox = region->data->numRects))
+    {
+        box_type_t * pbox_out;
+
+        for (pbox_out = pbox = PIXREGION_BOXPTR (region); nbox--; pbox++)
+        {
+            pbox_out->x1 = x1 = pbox->x1 + x;
+            pbox_out->y1 = y1 = pbox->y1 + y;
+            pbox_out->x2 = x2 = pbox->x2 + x;
+            pbox_out->y2 = y2 = pbox->y2 + y;
+
+            if (((x2 - PIXMAN_REGION_MIN) | (y2 - PIXMAN_REGION_MIN) |
+                 (PIXMAN_REGION_MAX - x1) | (PIXMAN_REGION_MAX - y1)) <= 0)
+            {
+                region->data->numRects--;
+                continue;
+        }
+
+            if (x1 < PIXMAN_REGION_MIN)
+        pbox_out->x1 = PIXMAN_REGION_MIN;
+            else if (x2 > PIXMAN_REGION_MAX)
+        pbox_out->x2 = PIXMAN_REGION_MAX;
+
+            if (y1 < PIXMAN_REGION_MIN)
+        pbox_out->y1 = PIXMAN_REGION_MIN;
+            else if (y2 > PIXMAN_REGION_MAX)
+        pbox_out->y2 = PIXMAN_REGION_MAX;
+
+            pbox_out++;
+    }
+
+        if (pbox_out != pbox)
+        {
+            if (region->data->numRects == 1)
+            {
+                region->extents = *PIXREGION_BOXPTR (region);
+                FREE_DATA (region);
+                region->data = (region_data_type_t *)NULL;
+        }
+            else
+        {
+        pixman_set_extents (region);
+        }
+    }
+    }
+
+    GOOD (region);
+}
+
+PIXMAN_EXPORT void
+PREFIX (_reset) (region_type_t *region, box_type_t *box)
+{
+    GOOD (region);
+
+    critical_if_fail (GOOD_RECT (box));
+
+    region->extents = *box;
+
+    FREE_DATA (region);
+
+    region->data = NULL;
+}
+
+PIXMAN_EXPORT void
+PREFIX (_clear) (region_type_t *region)
+{
+    GOOD (region);
+    FREE_DATA (region);
+
+    region->extents = *pixman_region_empty_box;
+    region->data = pixman_region_empty_data;
+}
+
+#if 0
+/* box is "return" value */
+PIXMAN_EXPORT int
+PREFIX (_contains_point) (region_type_t * region,
+                          int x, int y,
+                          box_type_t * box)
+{
+    box_type_t *pbox, *pbox_end;
+    int numRects;
+
+    GOOD (region);
+    numRects = PIXREGION_NUMRECTS (region);
+
+    if (!numRects || !INBOX (&region->extents, x, y))
+    return(FALSE);
+
+    if (numRects == 1)
+    {
+        if (box)
+        *box = region->extents;
+
+        return(TRUE);
+    }
+
+    pbox = PIXREGION_BOXPTR (region);
+    pbox_end = pbox + numRects;
+
+    pbox = find_box_for_y (pbox, pbox_end, y);
+
+    for (;pbox != pbox_end; pbox++)
+    {
+        if ((y < pbox->y1) || (x < pbox->x1))
+        break;              /* missed it */
+
+        if (x >= pbox->x2)
+        continue;           /* not there yet */
+
+        if (box)
+        *box = *pbox;
+
+        return(TRUE);
+    }
+
+    return(FALSE);
+}
+#endif
+
+PIXMAN_EXPORT int
+PREFIX (_not_empty) (region_type_t * region)
+{
+    GOOD (region);
+
+    return(!PIXREGION_NIL (region));
+}
+
+PIXMAN_EXPORT box_type_t *
+PREFIX (_extents) (region_type_t * region)
+{
+    GOOD (region);
+
+    return(&region->extents);
+}
+
+struct _SG_Region_Data
+{
+    int               ref;
+    region_type_t     impl;
+};
+
+inline static SG_Region region_copy(SG_Region *obj);
+
+static void
+detach(SG_Region *obj)
+{
+   if ( (obj->data->ref != 1) && (obj->data->ref != 0) )
+     {
+        //unref
+        obj->data->ref -= 1;
+        // copy
+        *obj = region_copy(obj);
+     }
+}
+
+inline static SG_Region
+region_ref(SG_Region *obj)
+{
+    obj->data->ref++;
+    return *obj;
+}
+
+inline static int
+region_rect_count(const SG_Region *obj)
+{
+    return PREFIX(_n_rects)(&obj->data->impl);
+}
+
+inline static Eina_Rect
+region_rect_at(const SG_Region *obj, int index)
+{
+    //pixman_region32_rectangles
+    box_type_t *box = (PIXREGION_RECTS (&obj->data->impl) + index);
+    // convert pixman_box to eina_rect
+    Eina_Rect r = EINA_RECT(box->x1, box->y1, box->x2 - box->x1, box->y2 - box->y1);
+    return r;
+}
+
+inline static void
+region_add_rect(SG_Region *obj, Eina_Rect r)
+{
+    detach(obj);
+    region_type_t *impl = &obj->data->impl;
+    PREFIX(_union_rect)(impl, impl, r.x, r.y, r.w, r.h);
+}
+
+inline static void
+region_substract_rect(SG_Region *obj, Eina_Rect r)
+{
+    detach(obj);
+    region_type_t *impl = &obj->data->impl;
+    region_type_t substract;
+    PREFIX(_init_rect)(&substract, r.x, r.y, r.w, r.h);
+    PREFIX(_subtract)(impl, impl, &substract);
+}
+
+inline static void
+region_intersect_rect(SG_Region *obj, Eina_Rect r)
+{
+    detach(obj);
+    region_type_t *impl = &obj->data->impl;
+    PREFIX(_intersect_rect)(impl, impl, r.x, r.y, r.w, r.h);
+}
+
+static void
+region_add_region(SG_Region *obj, SG_Region r)
+{
+    detach(obj);
+    PREFIX(_union)(&obj->data->impl, &obj->data->impl, &r.data->impl);
+}
+
+static void
+region_substract_region(SG_Region *obj, SG_Region r)
+{
+    detach(obj);
+    PREFIX(_subtract)(&obj->data->impl, &obj->data->impl, &r.data->impl);
+}
+
+static void
+region_intersect_region(SG_Region *obj, SG_Region r)
+{
+    detach(obj);
+    PREFIX(_intersect)(&obj->data->impl, &obj->data->impl, &r.data->impl);
+}
+
+static Eina_Bool
+region_equal(const SG_Region *obj, SG_Region r)
+{
+    return PREFIX(_equal)(&obj->data->impl, &r.data->impl);
+}
+
+static void
+region_clear(SG_Region *obj)
+{
+    detach(obj);
+    PREFIX(_clear)(&obj->data->impl);
+}
+
+static void
+region_reset(SG_Region *obj, Eina_Rect r)
+{
+    detach(obj);
+    box_type_t b = {r.x, r.y, r.x + r.w, r.y + r.h};
+    return PREFIX(_reset)(&obj->data->impl, &b);
+}
+
+static Eina_Bool
+region_empty(const SG_Region *obj)
+{
+    return (!PREFIX(_not_empty)(&obj->data->impl));
+}
+
+static Eina_Bool
+region_contains_rect(const SG_Region *obj, Eina_Rect r)
+{
+   box_type_t b = {r.x, r.y, r.x + r.w, r.y + r.h};
+   return (!PREFIX(_contains_rectangle)(&obj->data->impl, &b));
+}
+
+static void
+region_translate(SG_Region *obj, int x, int y)
+{
+    detach(obj);
+    PREFIX(_translate)(&obj->data->impl, x, y);
+}
+
+static Eina_Rect
+region_bounding_rect(const SG_Region *obj)
+{
+    box_type_t *b = PREFIX(_extents)(&obj->data->impl);
+
+    return EINA_RECT(b->x1, b->y1, b->x2 - b->x1, b->y2 - b->y1);
+}
+
+static SG_Region_Data SHARED_REGION_DATA = {2,{}};
+static SG_Region_Func   SG_REGION_VTABLE =
+{
+    region_copy,
+    region_ref,
+    region_rect_count,
+    region_rect_at,
+    region_add_rect,
+    region_substract_rect,
+    region_intersect_rect,
+    region_add_region,
+    region_substract_region,
+    region_intersect_region,
+    region_equal,
+    region_clear,
+    region_reset,
+    region_empty,
+    region_contains_rect,
+    region_translate,
+    region_bounding_rect
+};
+
+inline static SG_Region
+region_copy(SG_Region *obj)
+{
+   SG_Region r;
+
+   r.fn = &SG_REGION_VTABLE;
+   r.data = calloc(1, sizeof(SG_Region_Data));
+   r.data->ref = 1;
+   PREFIX(_copy)(&r.data->impl, &obj->data->impl);
+   return r;
+}
+
+SG_Region sg_region_new(void)
+{
+    SG_Region obj;
+
+    obj.fn = &SG_REGION_VTABLE;
+    obj.data = &SHARED_REGION_DATA;
+    obj.data->ref++;
+    PREFIX(_init)(&obj.data->impl);
+
+    return obj;
+}
+
+void sg_region_free(SG_Region *obj)
+{
+    obj->data->ref--;
+    if (!obj->data->ref)
+      {
+         PREFIX(_fini)(&obj->data->impl);
+         free(obj->data);
+      }
+}
diff --git a/src/static_libs/scenegraph/utils/sg_region.h b/src/static_libs/scenegraph/utils/sg_region.h
new file mode 100644
index 0000000000..1f4b8651a3
--- /dev/null
+++ b/src/static_libs/scenegraph/utils/sg_region.h
@@ -0,0 +1,41 @@
+#ifndef SG_REGION_H
+#define SG_REGION_H
+
+#include <Eina.h>
+
+typedef struct _SG_Region_Func          SG_Region_Func;
+typedef struct _SG_Region               SG_Region;
+typedef struct _SG_Region_Data          SG_Region_Data;
+
+struct _SG_Region_Func
+{
+    SG_Region      (*copy)(SG_Region *obj); //deep copy
+    SG_Region      (*ref)(SG_Region *obj); // shallow copy
+    int            (*rect_count)(const SG_Region *obj);
+    Eina_Rect      (*rect_at)(const SG_Region *obj, int index);
+    void           (*add_rect)(SG_Region *obj, Eina_Rect r);
+    void           (*substract_rect)(SG_Region *obj, Eina_Rect r);
+    void           (*intersect_rect)(SG_Region *obj, Eina_Rect r);
+    void           (*add_region)(SG_Region *obj, SG_Region r);
+    void           (*substract_region)(SG_Region *obj, SG_Region r);
+    void           (*intersect_region)(SG_Region *obj, SG_Region r);
+    Eina_Bool      (*equal)(const SG_Region *obj, SG_Region r);
+    void           (*clear)(SG_Region *obj);
+    void           (*reset)(SG_Region *obj, Eina_Rect r);
+    Eina_Bool      (*empty)(const SG_Region *obj);
+    Eina_Bool      (*contains_rect)(const SG_Region *obj, Eina_Rect r);
+    void           (*translate)(SG_Region *obj, int x, int y);
+    Eina_Rect      (*bounding_rect)(const SG_Region *obj);
+
+};
+
+SG_Region   sg_region_new(void);
+void        sg_region_free(SG_Region *obj);
+
+struct _SG_Region
+{
+    SG_Region_Func   *fn;
+    SG_Region_Data   *data;
+};
+
+#endif // SG_REGION_H