|
Packit |
1fb8d4 |
/**
|
|
Packit |
1fb8d4 |
* FreeRDP: A Remote Desktop Protocol Implementation
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Copyright 2014 Thincast Technologies GmbH
|
|
Packit |
1fb8d4 |
* Copyright 2014 Hardening <contact@hardening-consulting.com>
|
|
Packit |
1fb8d4 |
* Copyright 2017 Armin Novak <armin.novak@thincast.com>
|
|
Packit |
1fb8d4 |
* Copyright 2017 Thincast Technologies GmbH
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Licensed under the Apache License, Version 2.0 (the "License");
|
|
Packit |
1fb8d4 |
* you may not use this file except in compliance with the License.
|
|
Packit |
1fb8d4 |
* You may obtain a copy of the License at
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* http://www.apache.org/licenses/LICENSE-2.0
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Unless required by applicable law or agreed to in writing, software
|
|
Packit |
1fb8d4 |
* distributed under the License is distributed on an "AS IS" BASIS,
|
|
Packit |
1fb8d4 |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
Packit |
1fb8d4 |
* See the License for the specific language governing permissions and
|
|
Packit |
1fb8d4 |
* limitations under the License.
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
#include <assert.h>
|
|
Packit |
1fb8d4 |
#include <winpr/memory.h>
|
|
Packit |
1fb8d4 |
#include <freerdp/log.h>
|
|
Packit |
1fb8d4 |
#include <freerdp/codec/region.h>
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
#define TAG FREERDP_TAG("codec")
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/*
|
|
Packit |
1fb8d4 |
* The functions in this file implement the Region abstraction largely inspired from
|
|
Packit |
1fb8d4 |
* pixman library. The following comment is taken from the pixman code.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* A Region is simply a set of disjoint(non-overlapping) rectangles, plus an
|
|
Packit |
1fb8d4 |
* "extent" rectangle which is the smallest single rectangle that contains all
|
|
Packit |
1fb8d4 |
* the non-overlapping rectangles.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* A Region is implemented as a "y-x-banded" array of rectangles. This array
|
|
Packit |
1fb8d4 |
* imposes two degrees of order. First, all rectangles are sorted by top side
|
|
Packit |
1fb8d4 |
* y coordinate first (y1), and then by left side x coordinate (x1).
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Furthermore, the rectangles are grouped into "bands". Each rectangle in a
|
|
Packit |
1fb8d4 |
* band has the same top y coordinate (y1), and each has the same bottom y
|
|
Packit |
1fb8d4 |
* coordinate (y2). Thus all rectangles in a band differ only in their left
|
|
Packit |
1fb8d4 |
* and right side (x1 and x2). Bands are implicit in the array of rectangles:
|
|
Packit |
1fb8d4 |
* there is no separate list of band start pointers.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* The y-x band representation does not minimize rectangles. In particular,
|
|
Packit |
1fb8d4 |
* if a rectangle vertically crosses a band (the rectangle has scanlines in
|
|
Packit |
1fb8d4 |
* the y1 to y2 area spanned by the band), then the rectangle may be broken
|
|
Packit |
1fb8d4 |
* down into two or more smaller rectangles stacked one atop the other.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* ----------- -----------
|
|
Packit |
1fb8d4 |
* | | | | band 0
|
|
Packit |
1fb8d4 |
* | | -------- ----------- --------
|
|
Packit |
1fb8d4 |
* | | | | in y-x banded | | | | band 1
|
|
Packit |
1fb8d4 |
* | | | | form is | | | |
|
|
Packit |
1fb8d4 |
* ----------- | | ----------- --------
|
|
Packit |
1fb8d4 |
* | | | | band 2
|
|
Packit |
1fb8d4 |
* -------- --------
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* An added constraint on the rectangles is that they must cover as much
|
|
Packit |
1fb8d4 |
* horizontal area as possible: no two rectangles within a band are allowed
|
|
Packit |
1fb8d4 |
* to touch.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Whenever possible, bands will be merged together to cover a greater vertical
|
|
Packit |
1fb8d4 |
* distance (and thus reduce the number of rectangles). Two bands can be merged
|
|
Packit |
1fb8d4 |
* only if the bottom of one touches the top of the other and they have
|
|
Packit |
1fb8d4 |
* rectangles in the same places (of the same width, of course).
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
struct _REGION16_DATA
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
long size;
|
|
Packit |
1fb8d4 |
long nbRects;
|
|
Packit |
1fb8d4 |
};
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static REGION16_DATA empty_region = { 0, 0 };
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
void region16_init(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(region);
|
|
Packit |
1fb8d4 |
ZeroMemory(region, sizeof(REGION16));
|
|
Packit |
1fb8d4 |
region->data = &empty_region;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
int region16_n_rects(const REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(region);
|
|
Packit |
1fb8d4 |
assert(region->data);
|
|
Packit |
1fb8d4 |
return region->data->nbRects;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* region16_rects(const REGION16* region, UINT32* nbRects)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
REGION16_DATA* data;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (nbRects)
|
|
Packit |
1fb8d4 |
*nbRects = 0;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!region)
|
|
Packit |
1fb8d4 |
return NULL;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
data = region->data;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!data)
|
|
Packit |
1fb8d4 |
return NULL;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (nbRects)
|
|
Packit |
1fb8d4 |
*nbRects = data->nbRects;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return (RECTANGLE_16*)(data + 1);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static INLINE RECTANGLE_16* region16_rects_noconst(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
REGION16_DATA* data;
|
|
Packit |
1fb8d4 |
data = region->data;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!data)
|
|
Packit |
1fb8d4 |
return NULL;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return (RECTANGLE_16*)(&data[1]);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* region16_extents(const REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (!region)
|
|
Packit |
1fb8d4 |
return NULL;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return ®ion->extents;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static RECTANGLE_16* region16_extents_noconst(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (!region)
|
|
Packit |
1fb8d4 |
return NULL;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return ®ion->extents;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL rectangle_is_empty(const RECTANGLE_16* rect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* A rectangle with width = 0 or height = 0 should be regarded
|
|
Packit |
1fb8d4 |
* as empty.
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
return ((rect->left == rect->right) || (rect->top == rect->bottom)) ? TRUE : FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL region16_is_empty(const REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(region);
|
|
Packit |
1fb8d4 |
assert(region->data);
|
|
Packit |
1fb8d4 |
return (region->data->nbRects == 0);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL rectangles_equal(const RECTANGLE_16* r1, const RECTANGLE_16* r2)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
return ((r1->left == r2->left) && (r1->top == r2->top) &&
|
|
Packit |
1fb8d4 |
(r1->right == r2->right) && (r1->bottom == r2->bottom)) ? TRUE : FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL rectangles_intersects(const RECTANGLE_16* r1, const RECTANGLE_16* r2)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
RECTANGLE_16 tmp;
|
|
Packit |
1fb8d4 |
return rectangles_intersection(r1, r2, &tmp);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL rectangles_intersection(const RECTANGLE_16* r1, const RECTANGLE_16* r2,
|
|
Packit |
1fb8d4 |
RECTANGLE_16* dst)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dst->left = MAX(r1->left, r2->left);
|
|
Packit |
1fb8d4 |
dst->right = MIN(r1->right, r2->right);
|
|
Packit |
1fb8d4 |
dst->top = MAX(r1->top, r2->top);
|
|
Packit |
1fb8d4 |
dst->bottom = MIN(r1->bottom, r2->bottom);
|
|
Packit |
1fb8d4 |
return (dst->left < dst->right) && (dst->top < dst->bottom);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
void region16_clear(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(region);
|
|
Packit |
1fb8d4 |
assert(region->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (region->data->size)
|
|
Packit |
1fb8d4 |
free(region->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
region->data = &empty_region;
|
|
Packit |
1fb8d4 |
ZeroMemory(®ion->extents, sizeof(region->extents));
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static INLINE REGION16_DATA* allocateRegion(long nbItems)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
long allocSize = sizeof(REGION16_DATA) + (nbItems * sizeof(RECTANGLE_16));
|
|
Packit |
1fb8d4 |
REGION16_DATA* ret = (REGION16_DATA*) malloc(allocSize);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!ret)
|
|
Packit |
1fb8d4 |
return ret;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
ret->size = allocSize;
|
|
Packit |
1fb8d4 |
ret->nbRects = nbItems;
|
|
Packit |
1fb8d4 |
return ret;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL region16_copy(REGION16* dst, const REGION16* src)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(dst);
|
|
Packit |
1fb8d4 |
assert(dst->data);
|
|
Packit |
1fb8d4 |
assert(src);
|
|
Packit |
1fb8d4 |
assert(src->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (dst == src)
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dst->extents = src->extents;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (dst->data->size)
|
|
Packit |
1fb8d4 |
free(dst->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!src->data->size)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dst->data = &empty_region;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
else
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dst->data = allocateRegion(src->data->nbRects);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!dst->data)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
CopyMemory(dst->data, src->data, src->data->size);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
void region16_print(const REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* rects;
|
|
Packit |
1fb8d4 |
UINT32 nbRects, i;
|
|
Packit |
1fb8d4 |
int currentBandY = -1;
|
|
Packit |
1fb8d4 |
rects = region16_rects(region, &nbRects);
|
|
Packit |
1fb8d4 |
WLog_DBG(TAG, "nrects=%"PRIu32"", nbRects);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
for (i = 0; i < nbRects; i++, rects++)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (rects->top != currentBandY)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
currentBandY = rects->top;
|
|
Packit |
1fb8d4 |
WLog_DBG(TAG, "band %d: ", currentBandY);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
WLog_DBG(TAG, "(%"PRIu16",%"PRIu16"-%"PRIu16",%"PRIu16")", rects->left, rects->top, rects->right,
|
|
Packit |
1fb8d4 |
rects->bottom);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static void region16_copy_band_with_union(RECTANGLE_16* dst,
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* src, const RECTANGLE_16* end,
|
|
Packit |
1fb8d4 |
UINT16 newTop, UINT16 newBottom,
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* unionRect,
|
|
Packit |
1fb8d4 |
UINT32* dstCounter,
|
|
Packit |
1fb8d4 |
const RECTANGLE_16** srcPtr, RECTANGLE_16** dstPtr)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
UINT16 refY = src->top;
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* startOverlap, *endOverlap;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* merges a band with the given rect
|
|
Packit |
1fb8d4 |
* Input:
|
|
Packit |
1fb8d4 |
* unionRect
|
|
Packit |
1fb8d4 |
* | |
|
|
Packit |
1fb8d4 |
* | |
|
|
Packit |
1fb8d4 |
* ==============+===============+================================
|
|
Packit |
1fb8d4 |
* |Item1| |Item2| |Item3| |Item4| |Item5| Band
|
|
Packit |
1fb8d4 |
* ==============+===============+================================
|
|
Packit |
1fb8d4 |
* before | overlap | after
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* Resulting band:
|
|
Packit |
1fb8d4 |
* +-----+ +----------------------+ +-----+
|
|
Packit |
1fb8d4 |
* |Item1| | Item2 | |Item3|
|
|
Packit |
1fb8d4 |
* +-----+ +----------------------+ +-----+
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* We first copy as-is items that are before Item2, the first overlapping
|
|
Packit |
1fb8d4 |
* item.
|
|
Packit |
1fb8d4 |
* Then we find the last one that overlap unionRect to agregate Item2, Item3
|
|
Packit |
1fb8d4 |
* and Item4 to create Item2.
|
|
Packit |
1fb8d4 |
* Finally Item5 is copied as Item3.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* When no unionRect is provided, we skip the two first steps to just copy items
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (unionRect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* items before unionRect */
|
|
Packit |
1fb8d4 |
while ((src < end) && (src->top == refY) && (src->right < unionRect->left))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dst->top = newTop;
|
|
Packit |
1fb8d4 |
dst->bottom = newBottom;
|
|
Packit |
1fb8d4 |
dst->right = src->right;
|
|
Packit |
1fb8d4 |
dst->left = src->left;
|
|
Packit |
1fb8d4 |
src++;
|
|
Packit |
1fb8d4 |
dst++;
|
|
Packit |
1fb8d4 |
*dstCounter += 1;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* treat items overlapping with unionRect */
|
|
Packit |
1fb8d4 |
startOverlap = unionRect;
|
|
Packit |
1fb8d4 |
endOverlap = unionRect;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if ((src < end) && (src->top == refY) && (src->left < unionRect->left))
|
|
Packit |
1fb8d4 |
startOverlap = src;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
while ((src < end) && (src->top == refY) && (src->right < unionRect->right))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
src++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if ((src < end) && (src->top == refY) && (src->left < unionRect->right))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
endOverlap = src;
|
|
Packit |
1fb8d4 |
src++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dst->bottom = newBottom;
|
|
Packit |
1fb8d4 |
dst->top = newTop;
|
|
Packit |
1fb8d4 |
dst->left = startOverlap->left;
|
|
Packit |
1fb8d4 |
dst->right = endOverlap->right;
|
|
Packit |
1fb8d4 |
dst++;
|
|
Packit |
1fb8d4 |
*dstCounter += 1;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* treat remaining items on the same band */
|
|
Packit |
1fb8d4 |
while ((src < end) && (src->top == refY))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dst->top = newTop;
|
|
Packit |
1fb8d4 |
dst->bottom = newBottom;
|
|
Packit |
1fb8d4 |
dst->right = src->right;
|
|
Packit |
1fb8d4 |
dst->left = src->left;
|
|
Packit |
1fb8d4 |
src++;
|
|
Packit |
1fb8d4 |
dst++;
|
|
Packit |
1fb8d4 |
*dstCounter += 1;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (srcPtr)
|
|
Packit |
1fb8d4 |
*srcPtr = src;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
*dstPtr = dst;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static RECTANGLE_16* next_band(RECTANGLE_16* band1, RECTANGLE_16* endPtr, int* nbItems)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
UINT16 refY = band1->top;
|
|
Packit |
1fb8d4 |
*nbItems = 0;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
while ((band1 < endPtr) && (band1->top == refY))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
band1++;
|
|
Packit |
1fb8d4 |
*nbItems += 1;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return band1;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static BOOL band_match(const RECTANGLE_16* band1, const RECTANGLE_16* band2, RECTANGLE_16* endPtr)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
int refBand2 = band2->top;
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* band2Start = band2;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
while ((band1 < band2Start) && (band2 < endPtr) && (band2->top == refBand2))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if ((band1->left != band2->left) || (band1->right != band2->right))
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
band1++;
|
|
Packit |
1fb8d4 |
band2++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (band1 != band2Start)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return (band2 == endPtr) || (band2->top != refBand2);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/** compute if the rectangle is fully included in the band
|
|
Packit |
1fb8d4 |
* @param band a pointer on the beginning of the band
|
|
Packit |
1fb8d4 |
* @param endPtr end of the region
|
|
Packit |
1fb8d4 |
* @param rect the rectangle to test
|
|
Packit |
1fb8d4 |
* @return if rect is fully included in an item of the band
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
static BOOL rectangle_contained_in_band(const RECTANGLE_16* band, const RECTANGLE_16* endPtr,
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* rect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
UINT16 refY = band->top;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if ((band->top > rect->top) || (rect->bottom > band->bottom))
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* note: as the band is sorted from left to right, once we've seen an item
|
|
Packit |
1fb8d4 |
* that is after rect->left we're sure that the result is False.
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
while ((band < endPtr) && (band->top == refY) && (band->left <= rect->left))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (rect->right <= band->right)
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
band++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
static BOOL region16_simplify_bands(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/** Simplify consecutive bands that touch and have the same items
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* ==================== ====================
|
|
Packit |
1fb8d4 |
* | 1 | | 2 | | | | |
|
|
Packit |
1fb8d4 |
* ==================== | | | |
|
|
Packit |
1fb8d4 |
* | 1 | | 2 | ====> | 1 | | 2 |
|
|
Packit |
1fb8d4 |
* ==================== | | | |
|
|
Packit |
1fb8d4 |
* | 1 | | 2 | | | | |
|
|
Packit |
1fb8d4 |
* ==================== ====================
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
RECTANGLE_16* band1, *band2, *endPtr, *endBand, *tmp;
|
|
Packit |
1fb8d4 |
int nbRects, finalNbRects;
|
|
Packit |
1fb8d4 |
int bandItems, toMove;
|
|
Packit |
1fb8d4 |
finalNbRects = nbRects = region16_n_rects(region);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (nbRects < 2)
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
band1 = region16_rects_noconst(region);
|
|
Packit |
1fb8d4 |
endPtr = band1 + nbRects;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
do
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
band2 = next_band(band1, endPtr, &bandItems);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (band2 == endPtr)
|
|
Packit |
1fb8d4 |
break;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if ((band1->bottom == band2->top) && band_match(band1, band2, endPtr))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* adjust the bottom of band1 items */
|
|
Packit |
1fb8d4 |
tmp = band1;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
while (tmp < band2)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
tmp->bottom = band2->bottom;
|
|
Packit |
1fb8d4 |
tmp++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* override band2, we don't move band1 pointer as the band after band2
|
|
Packit |
1fb8d4 |
* may be merged too */
|
|
Packit |
1fb8d4 |
endBand = band2 + bandItems;
|
|
Packit |
1fb8d4 |
toMove = (endPtr - endBand) * sizeof(RECTANGLE_16);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (toMove)
|
|
Packit |
1fb8d4 |
MoveMemory(band2, endBand, toMove);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
finalNbRects -= bandItems;
|
|
Packit |
1fb8d4 |
endPtr -= bandItems;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
else
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
band1 = band2;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
while (TRUE);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (finalNbRects != nbRects)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
int allocSize = sizeof(REGION16_DATA) + (finalNbRects * sizeof(RECTANGLE_16));
|
|
Packit |
1fb8d4 |
region->data = realloc(region->data, allocSize);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!region->data)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
region->data = &empty_region;
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
region->data->nbRects = finalNbRects;
|
|
Packit |
1fb8d4 |
region->data->size = allocSize;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL region16_union_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* srcExtents;
|
|
Packit |
1fb8d4 |
RECTANGLE_16* dstExtents;
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* currentBand, *endSrcRect, *nextBand;
|
|
Packit |
1fb8d4 |
REGION16_DATA* newItems = NULL;
|
|
Packit |
1fb8d4 |
RECTANGLE_16* dstRect = NULL;
|
|
Packit |
1fb8d4 |
UINT32 usedRects, srcNbRects;
|
|
Packit |
1fb8d4 |
UINT16 topInterBand;
|
|
Packit |
1fb8d4 |
assert(src);
|
|
Packit |
1fb8d4 |
assert(src->data);
|
|
Packit |
1fb8d4 |
assert(dst);
|
|
Packit |
1fb8d4 |
srcExtents = region16_extents(src);
|
|
Packit |
1fb8d4 |
dstExtents = region16_extents_noconst(dst);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!region16_n_rects(src))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* source is empty, so the union is rect */
|
|
Packit |
1fb8d4 |
dst->extents = *rect;
|
|
Packit |
1fb8d4 |
dst->data = allocateRegion(1);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!dst->data)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dstRect = region16_rects_noconst(dst);
|
|
Packit |
1fb8d4 |
dstRect->top = rect->top;
|
|
Packit |
1fb8d4 |
dstRect->left = rect->left;
|
|
Packit |
1fb8d4 |
dstRect->right = rect->right;
|
|
Packit |
1fb8d4 |
dstRect->bottom = rect->bottom;
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
newItems = allocateRegion((1 + region16_n_rects(src)) * 4);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!newItems)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dstRect = (RECTANGLE_16*)(&newItems[1]);
|
|
Packit |
1fb8d4 |
usedRects = 0;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* adds the piece of rect that is on the top of src */
|
|
Packit |
1fb8d4 |
if (rect->top < srcExtents->top)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dstRect->top = rect->top;
|
|
Packit |
1fb8d4 |
dstRect->left = rect->left;
|
|
Packit |
1fb8d4 |
dstRect->right = rect->right;
|
|
Packit |
1fb8d4 |
dstRect->bottom = MIN(srcExtents->top, rect->bottom);
|
|
Packit |
1fb8d4 |
usedRects++;
|
|
Packit |
1fb8d4 |
dstRect++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* treat possibly overlapping region */
|
|
Packit |
1fb8d4 |
currentBand = region16_rects(src, &srcNbRects);
|
|
Packit |
1fb8d4 |
endSrcRect = currentBand + srcNbRects;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
while (currentBand < endSrcRect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if ((currentBand->bottom <= rect->top) || (rect->bottom <= currentBand->top) ||
|
|
Packit |
1fb8d4 |
rectangle_contained_in_band(currentBand, endSrcRect, rect))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* no overlap between rect and the band, rect is totally below or totally above
|
|
Packit |
1fb8d4 |
* the current band, or rect is already covered by an item of the band.
|
|
Packit |
1fb8d4 |
* let's copy all the rectangles from this band
|
|
Packit |
1fb8d4 |
+----+
|
|
Packit |
1fb8d4 |
| | rect (case 1)
|
|
Packit |
1fb8d4 |
+----+
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
=================
|
|
Packit |
1fb8d4 |
band of srcRect
|
|
Packit |
1fb8d4 |
=================
|
|
Packit |
1fb8d4 |
+----+
|
|
Packit |
1fb8d4 |
| | rect (case 2)
|
|
Packit |
1fb8d4 |
+----+
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
region16_copy_band_with_union(dstRect,
|
|
Packit |
1fb8d4 |
currentBand, endSrcRect,
|
|
Packit |
1fb8d4 |
currentBand->top, currentBand->bottom,
|
|
Packit |
1fb8d4 |
NULL, &usedRects,
|
|
Packit |
1fb8d4 |
&nextBand, &dstRect);
|
|
Packit |
1fb8d4 |
topInterBand = rect->top;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
else
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* rect overlaps the band:
|
|
Packit |
1fb8d4 |
| | | |
|
|
Packit |
1fb8d4 |
====^=================| |==| |=========================== band
|
|
Packit |
1fb8d4 |
| top split | | | |
|
|
Packit |
1fb8d4 |
v | 1 | | 2 |
|
|
Packit |
1fb8d4 |
^ | | | | +----+ +----+
|
|
Packit |
1fb8d4 |
| merge zone | | | | | | | 4 |
|
|
Packit |
1fb8d4 |
v +----+ | | | | +----+
|
|
Packit |
1fb8d4 |
^ | | | 3 |
|
|
Packit |
1fb8d4 |
| bottom split | | | |
|
|
Packit |
1fb8d4 |
====v=========================| |==| |===================
|
|
Packit |
1fb8d4 |
| | | |
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
possible cases:
|
|
Packit |
1fb8d4 |
1) no top split, merge zone then a bottom split. The band will be splitted
|
|
Packit |
1fb8d4 |
in two
|
|
Packit |
1fb8d4 |
2) not band split, only the merge zone, band merged with rect but not splitted
|
|
Packit |
1fb8d4 |
3) a top split, the merge zone and no bottom split. The band will be split
|
|
Packit |
1fb8d4 |
in two
|
|
Packit |
1fb8d4 |
4) a top split, the merge zone and also a bottom split. The band will be
|
|
Packit |
1fb8d4 |
splitted in 3, but the coalesce algorithm may merge the created bands
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
UINT16 mergeTop = currentBand->top;
|
|
Packit |
1fb8d4 |
UINT16 mergeBottom = currentBand->bottom;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* test if we need a top split, case 3 and 4 */
|
|
Packit |
1fb8d4 |
if (rect->top > currentBand->top)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
region16_copy_band_with_union(dstRect,
|
|
Packit |
1fb8d4 |
currentBand, endSrcRect,
|
|
Packit |
1fb8d4 |
currentBand->top, rect->top,
|
|
Packit |
1fb8d4 |
NULL, &usedRects,
|
|
Packit |
1fb8d4 |
&nextBand, &dstRect);
|
|
Packit |
1fb8d4 |
mergeTop = rect->top;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* do the merge zone (all cases) */
|
|
Packit |
1fb8d4 |
if (rect->bottom < currentBand->bottom)
|
|
Packit |
1fb8d4 |
mergeBottom = rect->bottom;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
region16_copy_band_with_union(dstRect,
|
|
Packit |
1fb8d4 |
currentBand, endSrcRect,
|
|
Packit |
1fb8d4 |
mergeTop, mergeBottom,
|
|
Packit |
1fb8d4 |
rect, &usedRects,
|
|
Packit |
1fb8d4 |
&nextBand, &dstRect);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* test if we need a bottom split, case 1 and 4 */
|
|
Packit |
1fb8d4 |
if (rect->bottom < currentBand->bottom)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
region16_copy_band_with_union(dstRect,
|
|
Packit |
1fb8d4 |
currentBand, endSrcRect,
|
|
Packit |
1fb8d4 |
mergeBottom, currentBand->bottom,
|
|
Packit |
1fb8d4 |
NULL, &usedRects,
|
|
Packit |
1fb8d4 |
&nextBand, &dstRect);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
topInterBand = currentBand->bottom;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* test if a piece of rect should be inserted as a new band between
|
|
Packit |
1fb8d4 |
* the current band and the next one. band n and n+1 shouldn't touch.
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
* ==============================================================
|
|
Packit |
1fb8d4 |
* band n
|
|
Packit |
1fb8d4 |
* +------+ +------+
|
|
Packit |
1fb8d4 |
* ===========| rect |====================| |===============
|
|
Packit |
1fb8d4 |
* | | +------+ | |
|
|
Packit |
1fb8d4 |
* +------+ | rect | | rect |
|
|
Packit |
1fb8d4 |
* +------+ | |
|
|
Packit |
1fb8d4 |
* =======================================| |================
|
|
Packit |
1fb8d4 |
* +------+ band n+1
|
|
Packit |
1fb8d4 |
* ===============================================================
|
|
Packit |
1fb8d4 |
*
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
if ((nextBand < endSrcRect) && (nextBand->top != currentBand->bottom) &&
|
|
Packit |
1fb8d4 |
(rect->bottom > currentBand->bottom) && (rect->top < nextBand->top))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dstRect->right = rect->right;
|
|
Packit |
1fb8d4 |
dstRect->left = rect->left;
|
|
Packit |
1fb8d4 |
dstRect->top = topInterBand;
|
|
Packit |
1fb8d4 |
dstRect->bottom = MIN(nextBand->top, rect->bottom);
|
|
Packit |
1fb8d4 |
dstRect++;
|
|
Packit |
1fb8d4 |
usedRects++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
currentBand = nextBand;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* adds the piece of rect that is below src */
|
|
Packit |
1fb8d4 |
if (srcExtents->bottom < rect->bottom)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
dstRect->top = MAX(srcExtents->bottom, rect->top);
|
|
Packit |
1fb8d4 |
dstRect->left = rect->left;
|
|
Packit |
1fb8d4 |
dstRect->right = rect->right;
|
|
Packit |
1fb8d4 |
dstRect->bottom = rect->bottom;
|
|
Packit |
1fb8d4 |
usedRects++;
|
|
Packit |
1fb8d4 |
dstRect++;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if ((src == dst) && (src->data->size))
|
|
Packit |
1fb8d4 |
free(src->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dstExtents->top = MIN(rect->top, srcExtents->top);
|
|
Packit |
1fb8d4 |
dstExtents->left = MIN(rect->left, srcExtents->left);
|
|
Packit |
1fb8d4 |
dstExtents->bottom = MAX(rect->bottom, srcExtents->bottom);
|
|
Packit |
1fb8d4 |
dstExtents->right = MAX(rect->right, srcExtents->right);
|
|
Packit |
1fb8d4 |
newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16));
|
|
Packit |
1fb8d4 |
dst->data = realloc(newItems, newItems->size);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!dst->data)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
free(newItems);
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dst->data->nbRects = usedRects;
|
|
Packit |
1fb8d4 |
return region16_simplify_bands(dst);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL region16_intersects_rect(const REGION16* src, const RECTANGLE_16* arg2)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* rect, *endPtr, *srcExtents;
|
|
Packit |
1fb8d4 |
UINT32 nbRects;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!src || !src->data || !arg2)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
rect = region16_rects(src, &nbRects);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!nbRects)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
srcExtents = region16_extents(src);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (nbRects == 1)
|
|
Packit |
1fb8d4 |
return rectangles_intersects(srcExtents, arg2);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!rectangles_intersects(srcExtents, arg2))
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
for (endPtr = rect + nbRects; (rect < endPtr) && (arg2->bottom > rect->top); rect++)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (rectangles_intersects(rect, arg2))
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
BOOL region16_intersect_rect(REGION16* dst, const REGION16* src, const RECTANGLE_16* rect)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
REGION16_DATA* newItems;
|
|
Packit |
1fb8d4 |
const RECTANGLE_16* srcPtr, *endPtr, *srcExtents;
|
|
Packit |
1fb8d4 |
RECTANGLE_16* dstPtr;
|
|
Packit |
1fb8d4 |
UINT32 nbRects, usedRects;
|
|
Packit |
1fb8d4 |
RECTANGLE_16 common, newExtents;
|
|
Packit |
1fb8d4 |
assert(src);
|
|
Packit |
1fb8d4 |
assert(src->data);
|
|
Packit |
1fb8d4 |
srcPtr = region16_rects(src, &nbRects);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!nbRects)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
region16_clear(dst);
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
srcExtents = region16_extents(src);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (nbRects == 1)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
BOOL intersects = rectangles_intersection(srcExtents, rect, &common);
|
|
Packit |
1fb8d4 |
region16_clear(dst);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (intersects)
|
|
Packit |
1fb8d4 |
return region16_union_rect(dst, dst, &common);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
return TRUE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
newItems = allocateRegion(nbRects);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!newItems)
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dstPtr = (RECTANGLE_16*)(&newItems[1]);
|
|
Packit |
1fb8d4 |
usedRects = 0;
|
|
Packit |
1fb8d4 |
ZeroMemory(&newExtents, sizeof(newExtents));
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
/* accumulate intersecting rectangles, the final region16_simplify_bands() will
|
|
Packit |
1fb8d4 |
* do all the bad job to recreate correct rectangles
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
for (endPtr = srcPtr + nbRects; (srcPtr < endPtr) && (rect->bottom > srcPtr->top); srcPtr++)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (rectangles_intersection(srcPtr, rect, &common))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
*dstPtr = common;
|
|
Packit |
1fb8d4 |
usedRects++;
|
|
Packit |
1fb8d4 |
dstPtr++;
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (rectangle_is_empty(&newExtents))
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
/* Check if the existing newExtents is empty. If it is empty, use
|
|
Packit |
1fb8d4 |
* new common directly. We do not need to check common rectangle
|
|
Packit |
1fb8d4 |
* because the rectangles_intersection() ensures that it is not empty.
|
|
Packit |
1fb8d4 |
*/
|
|
Packit |
1fb8d4 |
newExtents = common;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
else
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
newExtents.top = MIN(common.top, newExtents.top);
|
|
Packit |
1fb8d4 |
newExtents.left = MIN(common.left, newExtents.left);
|
|
Packit |
1fb8d4 |
newExtents.bottom = MAX(common.bottom, newExtents.bottom);
|
|
Packit |
1fb8d4 |
newExtents.right = MAX(common.right, newExtents.right);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
newItems->nbRects = usedRects;
|
|
Packit |
1fb8d4 |
newItems->size = sizeof(REGION16_DATA) + (usedRects * sizeof(RECTANGLE_16));
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (dst->data->size)
|
|
Packit |
1fb8d4 |
free(dst->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dst->data = realloc(newItems, newItems->size);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (!dst->data)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
free(newItems);
|
|
Packit |
1fb8d4 |
return FALSE;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
dst->extents = newExtents;
|
|
Packit |
1fb8d4 |
return region16_simplify_bands(dst);
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
void region16_uninit(REGION16* region)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
assert(region);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
if (region->data)
|
|
Packit |
1fb8d4 |
{
|
|
Packit |
1fb8d4 |
if (region->data->size)
|
|
Packit |
1fb8d4 |
free(region->data);
|
|
Packit |
1fb8d4 |
|
|
Packit |
1fb8d4 |
region->data = NULL;
|
|
Packit |
1fb8d4 |
}
|
|
Packit |
1fb8d4 |
}
|