pixman-region.c

嵌入式图形库

/*ARGSUSED*/
static pixman_bool_t
pixman_region_intersectO (pixman_region16_t *region,
			  pixman_box16_t    *r1,
			  pixman_box16_t    *r1End,
			  pixman_box16_t    *r2,
			  pixman_box16_t    *r2End,
			  short    	     y1,
			  short    	     y2,
			  int		    *pOverlap)
{
    int  	x1;
    int  	x2;
    pixman_box16_t *	pNextRect;

    pNextRect = PIXREGION_TOP(region);

    assert(y1 < y2);
    assert(r1 != r1End && r2 != r2End);

    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, pNextRect, 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 != r1End) && (r2 != r2End));

    return TRUE;
}

pixman_bool_t
pixman_region_intersect (pixman_region16_t * 	newReg,
			 pixman_region16_t * 	reg1,
			 pixman_region16_t *	reg2)
{
    good(reg1);
    good(reg2);
    good(newReg);
   /* check for trivial reject */
    if (PIXREGION_NIL(reg1)  || PIXREGION_NIL(reg2) ||
	!EXTENTCHECK(&reg1->extents, &reg2->extents))
    {
	/* Covers about 20% of all cases */
	freeData(newReg);
	newReg->extents.x2 = newReg->extents.x1;
	newReg->extents.y2 = newReg->extents.y1;
	if (PIXREGION_NAR(reg1) || PIXREGION_NAR(reg2))
	{
	    newReg->data = pixman_brokendata;
	    return FALSE;
	}
	else
	    newReg->data = pixman_region_emptyData;
    }
    else if (!reg1->data && !reg2->data)
    {
	/* Covers about 80% of cases that aren't trivially rejected */
	newReg->extents.x1 = MAX(reg1->extents.x1, reg2->extents.x1);
	newReg->extents.y1 = MAX(reg1->extents.y1, reg2->extents.y1);
	newReg->extents.x2 = MIN(reg1->extents.x2, reg2->extents.x2);
	newReg->extents.y2 = MIN(reg1->extents.y2, reg2->extents.y2);
	freeData(newReg);
	newReg->data = (pixman_region16_data_t *)NULL;
    }
    else if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
    {
	return pixman_region_copy(newReg, reg1);
    }
    else if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
    {
	return pixman_region_copy(newReg, reg2);
    }
    else if (reg1 == reg2)
    {
	return pixman_region_copy(newReg, reg1);
    }
    else
    {
	/* General purpose intersection */
	int overlap; /* result ignored */
	if (!pixman_op(newReg, reg1, reg2, pixman_region_intersectO, FALSE, FALSE,
			&overlap))
	    return FALSE;
	pixman_set_extents(newReg);
    }

    good(newReg);
    return(TRUE);
}

#define MERGERECT(r)						\
{								\
    if (r->x1 <= x2) {						\
	/* Merge with current rectangle */			\
	if (r->x1 < x2) *pOverlap = TRUE;				\
	if (x2 < r->x2) x2 = r->x2;				\
    } else {							\
	/* Add current rectangle, start new one */		\
	NEWRECT(region, pNextRect, x1, y1, x2, y2);		\
	x1 = r->x1;						\
	x2 = r->x2;						\
    }								\
    r++;							\
}

/*======================================================================
 *	    Region Union
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * pixman_region_unionO --
 *	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.
 *	pOverlap is set to TRUE if any boxes overlap.
 *
 *-----------------------------------------------------------------------
 */
static pixman_bool_t
pixman_region_unionO (
    pixman_region16_t	 *region,
    pixman_box16_t *r1,
    pixman_box16_t *r1End,
    pixman_box16_t *r2,
    pixman_box16_t *r2End,
    short	  y1,
    short	  y2,
    int		  *pOverlap)
{
    pixman_box16_t *     pNextRect;
    int        x1;     /* left and right side of current union */
    int        x2;

    assert (y1 < y2);
    assert(r1 != r1End && r2 != r2End);

    pNextRect = 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 != r1End && r2 != r2End)
    {
	if (r1->x1 < r2->x1) MERGERECT(r1) else MERGERECT(r2);
    }

    /* Finish off whoever (if any) is left */
    if (r1 != r1End)
    {
	do
	{
	    MERGERECT(r1);
	} while (r1 != r1End);
    }
    else if (r2 != r2End)
    {
	do
	{
	    MERGERECT(r2);
	} while (r2 != r2End);
    }

    /* Add current rectangle */
    NEWRECT(region, pNextRect, x1, y1, x2, y2);

    return TRUE;
}

/* Convenience function for performing union of region with a
 * single rectangle
 */
pixman_bool_t
pixman_region_union_rect (pixman_region16_t *dest,
			  pixman_region16_t *source,
			  int x, int y,
			  unsigned int width, unsigned int height)
{
    pixman_region16_t region;

    if (!width || !height)
	return pixman_region_copy (dest, source);
    region.data = NULL;
    region.extents.x1 = x;
    region.extents.y1 = y;
    region.extents.x2 = x + width;
    region.extents.y2 = y + height;

    return pixman_region_union (dest, source, &region);
}

pixman_bool_t
pixman_region_union (pixman_region16_t *newReg,
		     pixman_region16_t *reg1,
		     pixman_region16_t *reg2)
{
    int overlap; /* result ignored */

    /* Return TRUE if some overlap
     * between reg1, reg2
     */
    good(reg1);
    good(reg2);
    good(newReg);
    /*  checks all the simple cases */

    /*
     * Region 1 and 2 are the same
     */
    if (reg1 == reg2)
    {
	return pixman_region_copy(newReg, reg1);
    }

    /*
     * Region 1 is empty
     */
    if (PIXREGION_NIL(reg1))
    {
	if (PIXREGION_NAR(reg1))
	    return pixman_break (newReg);
        if (newReg != reg2)
	    return pixman_region_copy(newReg, reg2);
        return TRUE;
    }

    /*
     * Region 2 is empty
     */
    if (PIXREGION_NIL(reg2))
    {
	if (PIXREGION_NAR(reg2))
	    return pixman_break (newReg);
        if (newReg != reg1)
	    return pixman_region_copy(newReg, reg1);
        return TRUE;
    }

    /*
     * Region 1 completely subsumes region 2
     */
    if (!reg1->data && SUBSUMES(&reg1->extents, &reg2->extents))
    {
        if (newReg != reg1)
	    return pixman_region_copy(newReg, reg1);
        return TRUE;
    }

    /*
     * Region 2 completely subsumes region 1
     */
    if (!reg2->data && SUBSUMES(&reg2->extents, &reg1->extents))
    {
        if (newReg != reg2)
	    return pixman_region_copy(newReg, reg2);
        return TRUE;
    }

    if (!pixman_op(newReg, reg1, reg2, pixman_region_unionO, TRUE, TRUE, &overlap))
	return FALSE;

    newReg->extents.x1 = MIN(reg1->extents.x1, reg2->extents.x1);
    newReg->extents.y1 = MIN(reg1->extents.y1, reg2->extents.y1);
    newReg->extents.x2 = MAX(reg1->extents.x2, reg2->extents.x2);
    newReg->extents.y2 = MAX(reg1->extents.y2, reg2->extents.y2);
    good(newReg);
    return TRUE;
}

/*======================================================================
 *	    Batch Rectangle Union
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * pixman_region_append --
 *
 *      "Append" the rgn rectangles onto the end of dstrgn, maintaining
 *      knowledge of YX-banding when it's easy.  Otherwise, dstrgn just
 *      becomes a non-y-x-banded random collection of rectangles, and not
 *      yet a true region.  After a sequence of appends, the caller must
 *      call pixman_region_validate to ensure that a valid region is
 *      constructed.
 *
 * Results:
 *	TRUE if successful.
 *
 * Side Effects:
 *      dstrgn is modified if rgn has rectangles.
 *
 */
pixman_bool_t
pixman_region_append (pixman_region16_t * dstrgn,
		      pixman_region16_t * rgn)
{
    int numRects, dnumRects, size;
    pixman_box16_t *new, *old;
    int prepend;

    if (PIXREGION_NAR(rgn))
	return pixman_break (dstrgn);

    if (!rgn->data && (dstrgn->data == pixman_region_emptyData))
    {
	dstrgn->extents = rgn->extents;
	dstrgn->data = (pixman_region16_data_t *)NULL;
	return TRUE;
    }

    numRects = PIXREGION_NUM_RECTS(rgn);
    if (!numRects)
	return TRUE;
    prepend = FALSE;
    size = numRects;
    dnumRects = PIXREGION_NUM_RECTS(dstrgn);
    if (!dnumRects && (size < 200))
	size = 200; /* XXX pick numbers out of a hat */
    RECTALLOC(dstrgn, size);
    old = PIXREGION_RECTS(rgn);
    if (!dnumRects)
	dstrgn->extents = rgn->extents;
    else if (dstrgn->extents.x2 > dstrgn->extents.x1)
    {
	pixman_box16_t *first, *last;

	first = old;
	last = PIXREGION_BOXPTR(dstrgn) + (dnumRects - 1);
	if ((first->y1 > last->y2) ||
	    ((first->y1 == last->y1) && (first->y2 == last->y2) &&
	     (first->x1 > last->x2)))
	{
	    if (rgn->extents.x1 < dstrgn->extents.x1)
		dstrgn->extents.x1 = rgn->extents.x1;
	    if (rgn->extents.x2 > dstrgn->extents.x2)
		dstrgn->extents.x2 = rgn->extents.x2;
	    dstrgn->extents.y2 = rgn->extents.y2;
	}
	else
	{
	    first = PIXREGION_BOXPTR(dstrgn);
	    last = old + (numRects - 1);
	    if ((first->y1 > last->y2) ||
		((first->y1 == last->y1) && (first->y2 == last->y2) &&
		 (first->x1 > last->x2)))
	    {
		prepend = TRUE;
		if (rgn->extents.x1 < dstrgn->extents.x1)
		    dstrgn->extents.x1 = rgn->extents.x1;
		if (rgn->extents.x2 > dstrgn->extents.x2)
		    dstrgn->extents.x2 = rgn->extents.x2;
		dstrgn->extents.y1 = rgn->extents.y1;
	    }
	    else
		dstrgn->extents.x2 = dstrgn->extents.x1;
	}
    }
    if (prepend)
    {
	new = PIXREGION_BOX(dstrgn, numRects);
	if (dnumRects == 1)
	    *new = *PIXREGION_BOXPTR(dstrgn);
	else
	    memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn),
		  dnumRects * sizeof(pixman_box16_t));
	new = PIXREGION_BOXPTR(dstrgn);
    }
    else
	new = PIXREGION_BOXPTR(dstrgn) + dnumRects;
    if (numRects == 1)
	*new = *old;
    else
	memmove((char *)new, (char *)old, numRects * sizeof(pixman_box16_t));
    dstrgn->data->numRects += numRects;
    return TRUE;
}

#define ExchangeRects(a, b) \
{			    \
    pixman_box16_t     t;	    \
    t = rects[a];	    \
    rects[a] = rects[b];    \
    rects[b] = t;	    \
}

static void
QuickSortRects(
    pixman_box16_t     rects[],
    int        numRects)
{
    int	y1;
    int	x1;
    int        i, j;
    pixman_box16_t *r;

    /* Always called with numRects > 1 */

    do
    {
	if (numRects == 2)
	{
	    if (rects[0].y1 > rects[1].y1 ||
		    (rects[0].y1 == rects[1].y1 && rects[0].x1 > rects[1].x1))
		ExchangeRects(0, 1);
	    return;
	}

	/* Choose partition element, stick in location 0 */
        ExchangeRects(0, numRects >> 1);
	y1 = rects[0].y1;
	x1 = rects[0].x1;

        /* Partition array */
        i = 0;
        j = numRects;
        do
	{
	    r = &(rects[i]);
	    do
	    {
		r++;
		i++;
            } while (i != numRects &&
		     (r->y1 < y1 || (r->y1 == y1 && r->x1 < x1)));
	    r = &(rects[j]);
	    do
	    {
		r--;
		j--;
            } while (y1 < r->y1 || (y1 == r->y1 && x1 < r->x1));
            if (i < j)
		ExchangeRects(i, j);
        } while (i < j);

        /* Move partition element back to middle */