/* * File : region.c * This file is part of RT-Thread RTOS * COPYRIGHT (C) 2006 - 2009, RT-Thread Development Team * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rt-thread.org/license/LICENSE * * Change Logs: * Date Author Notes * 2009-10-16 Bernard first version */ #include #include /* #define good(reg) RT_ASSERT(rtgui_region16_valid(reg)) */ #define good(reg) #define RTGUI_MIN(a,b) ((a) < (b) ? (a) : (b)) #define RTGUI_MAX(a,b) ((a) > (b) ? (a) : (b)) #define RTGUI_SHRT_MIN (-32767-1) #define RTGUI_SHRT_MAX 32767 #define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects) /* not a region */ #define PIXREGION_NAR(reg) ((reg)->data == &rtgui_brokendata) #define PIXREGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1) #define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0) #define PIXREGION_RECTS(reg) ((reg)->data ? (rtgui_rect_t *)((reg)->data + 1) \ : &(reg)->extents) #define PIXREGION_BOXPTR(reg) ((rtgui_rect_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 PIXREGION_SZOF(n) (sizeof(rtgui_region_data_t) + ((n) * sizeof(rtgui_rect_t))) rtgui_rect_t rtgui_empty_rect = {0, 0, 0, 0}; rtgui_point_t rtgui_empty_point = {0, 0}; static rtgui_region_data_t rtgui_region_emptydata = {0, 0}; static rtgui_region_data_t rtgui_brokendata = {0, 0}; static rtgui_region_status_t rtgui_break(rtgui_region_t *pReg); /* * 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 RTGUI_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 rtgui_region_validate in order to support several speed improvements to * rtgui_region_validateTree. 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. */ /* 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) ) #define allocData(n) rtgui_malloc(PIXREGION_SZOF(n)) #define freeData(reg) if ((reg)->data && (reg)->data->size) rtgui_free((reg)->data) #define RECTALLOC_BAIL(pReg,n,bail) \ if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ if (!rtgui_rect_alloc(pReg, n)) { goto bail; } #define RECTALLOC(pReg,n) \ if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \ if (!rtgui_rect_alloc(pReg, n)) { return RTGUI_REGION_STATUS_FAILURE; } #define ADDRECT(pNextRect,nx1,ny1,nx2,ny2) \ { \ pNextRect->x1 = nx1; \ pNextRect->y1 = ny1; \ pNextRect->x2 = nx2; \ pNextRect->y2 = ny2; \ pNextRect++; \ } #define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2) \ { \ if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\ { \ if (!rtgui_rect_alloc(pReg, 1)) \ return RTGUI_REGION_STATUS_FAILURE; \ pNextRect = PIXREGION_TOP(pReg); \ } \ ADDRECT(pNextRect,nx1,ny1,nx2,ny2); \ pReg->data->numRects++; \ RT_ASSERT(pReg->data->numRects<=pReg->data->size); \ } #define DOWNSIZE(reg,numRects) \ if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \ { \ rtgui_region_data_t * NewData; \ NewData = (rtgui_region_data_t *)rt_realloc((reg)->data, PIXREGION_SZOF(numRects)); \ if (NewData) \ { \ NewData->size = (numRects); \ (reg)->data = NewData; \ } \ } void rtgui_region_init(rtgui_region_t *region) { region->extents = rtgui_empty_rect; region->data = &rtgui_region_emptydata; } void rtgui_region_init_rect(rtgui_region_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; region->data = RT_NULL; } void rtgui_region_init_with_extents(rtgui_region_t *region, rtgui_rect_t *extents) { region->extents = *extents; region->data = RT_NULL; } void rtgui_region_fini (rtgui_region_t *region) { good (region); freeData (region); } int rtgui_region_num_rects (rtgui_region_t *region) { return PIXREGION_NUM_RECTS (region); } rtgui_rect_t *rtgui_region_rects (rtgui_region_t *region) { return PIXREGION_RECTS (region); } static rtgui_region_status_t rtgui_break (rtgui_region_t *region) { freeData (region); region->extents = rtgui_empty_rect; region->data = &rtgui_brokendata; return RTGUI_REGION_STATUS_FAILURE; } static rtgui_region_status_t rtgui_rect_alloc(rtgui_region_t * region, int n) { rtgui_region_data_t *data; if (!region->data) { n++; region->data = allocData(n); if (!region->data) return rtgui_break (region); region->data->numRects = 1; *PIXREGION_BOXPTR(region) = region->extents; } else if (!region->data->size) { region->data = allocData(n); if (!region->data) return rtgui_break (region); region->data->numRects = 0; } else { if (n == 1) { n = region->data->numRects; if (n > 500) /* XXX pick numbers out of a hat */ n = 250; } n += region->data->numRects; data = (rtgui_region_data_t *)rt_realloc(region->data, PIXREGION_SZOF(n)); if (!data) return rtgui_break (region); region->data = data; } region->data->size = n; return RTGUI_REGION_STATUS_SUCCESS; } rtgui_region_status_t rtgui_region_copy(rtgui_region_t *dst, rtgui_region_t *src) { good(dst); good(src); if (dst == src) return RTGUI_REGION_STATUS_SUCCESS; dst->extents = src->extents; if (!src->data || !src->data->size) { freeData(dst); dst->data = src->data; return RTGUI_REGION_STATUS_SUCCESS; } if (!dst->data || (dst->data->size < src->data->numRects)) { freeData(dst); dst->data = allocData(src->data->numRects); if (!dst->data) return rtgui_break (dst); dst->data->size = src->data->numRects; } dst->data->numRects = src->data->numRects; rt_memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src), dst->data->numRects * sizeof(rtgui_rect_t)); return RTGUI_REGION_STATUS_SUCCESS; } /*====================================================================== * Generic Region Operator *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_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 rtgui_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. * *----------------------------------------------------------------------- */ rt_inline int rtgui_coalesce ( rtgui_region_t *region, /* Region to coalesce */ int prevStart, /* Index of start of previous band */ int curStart) /* Index of start of current band */ { rtgui_rect_t * pPrevBox; /* Current box in previous band */ rtgui_rect_t * pCurBox; /* 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 = curStart - prevStart; RT_ASSERT(numRects == region->data->numRects - curStart); if (!numRects) return curStart; /* * The bands may only be coalesced if the bottom of the previous * matches the top scanline of the current. */ pPrevBox = PIXREGION_BOX(region, prevStart); pCurBox = PIXREGION_BOX(region, curStart); if (pPrevBox->y2 != pCurBox->y1) return curStart; /* * 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 = pCurBox->y2; do { if ((pPrevBox->x1 != pCurBox->x1) || (pPrevBox->x2 != pCurBox->x2)) { return (curStart); } pPrevBox++; pCurBox++; 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 = curStart - prevStart; region->data->numRects -= numRects; do { pPrevBox--; pPrevBox->y2 = y2; numRects--; } while (numRects); return prevStart; } /* Quicky macro to avoid trivial reject procedure calls to rtgui_coalesce */ #define Coalesce(newReg, prevBand, curBand) \ if (curBand - prevBand == newReg->data->numRects - curBand) { \ prevBand = rtgui_coalesce(newReg, prevBand, curBand); \ } else { \ prevBand = curBand; \ } /*- *----------------------------------------------------------------------- * rtgui_region_appendNonO -- * 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. * *----------------------------------------------------------------------- */ rt_inline rtgui_region_status_t rtgui_region_appendNonO ( rtgui_region_t *region, rtgui_rect_t *r, rtgui_rect_t *rEnd, int y1, int y2) { rtgui_rect_t * pNextRect; int newRects; newRects = rEnd - r; RT_ASSERT(y1 < y2); RT_ASSERT(newRects != 0); /* Make sure we have enough space for all rectangles to be added */ RECTALLOC(region, newRects); pNextRect = PIXREGION_TOP(region); region->data->numRects += newRects; do { RT_ASSERT(r->x1 < r->x2); ADDRECT(pNextRect, r->x1, y1, r->x2, y2); r++; } while (r != rEnd); return RTGUI_REGION_STATUS_SUCCESS; } #define FindBand(r, rBandEnd, rEnd, ry1) \ { \ ry1 = r->y1; \ rBandEnd = r+1; \ while ((rBandEnd != rEnd) && (rBandEnd->y1 == ry1)) { \ rBandEnd++; \ } \ } #define AppendRegions(newReg, r, rEnd) \ { \ int newRects = rEnd - r; \ if (newRects) { \ RECTALLOC(newReg, newRects); \ rt_memmove((char *)PIXREGION_TOP(newReg),(char *)r, \ newRects * sizeof(rtgui_rect_t)); \ newReg->data->numRects += newRects; \ } \ } /*- *----------------------------------------------------------------------- * rtgui_op -- * Apply an operation to two regions. Called by rtgui_region_union, rtgui_region_inverse, * rtgui_region_subtract, rtgui_region_intersect.... Both regions MUST have at least one * rectangle, and cannot be the same object. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * The new region is overwritten. * pOverlap set to RTGUI_REGION_STATUS_SUCCESS if overlapFunc ever returns RTGUI_REGION_STATUS_SUCCESS. * * 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 nonOverlapFunc is called with * each the band and the band's upper and lower extents. For the * second, the overlapFunc 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 rtgui_region_status_t (*OverlapProcPtr)( rtgui_region_t *region, rtgui_rect_t *r1, rtgui_rect_t *r1End, rtgui_rect_t *r2, rtgui_rect_t *r2End, short y1, short y2, int *pOverlap); static rtgui_region_status_t rtgui_op( rtgui_region_t *newReg, /* Place to store result */ rtgui_region_t *reg1, /* First region in operation */ rtgui_region_t *reg2, /* 2d region in operation */ OverlapProcPtr overlapFunc, /* Function to call for over- * lapping bands */ int appendNon1, /* Append non-overlapping bands */ /* in region 1 ? */ int appendNon2, /* Append non-overlapping bands */ /* in region 2 ? */ int *pOverlap) { rtgui_rect_t * r1; /* Pointer into first region */ rtgui_rect_t * r2; /* Pointer into 2d region */ rtgui_rect_t * r1End; /* End of 1st region */ rtgui_rect_t * r2End; /* End of 2d region */ short ybot; /* Bottom of intersection */ short ytop; /* Top of intersection */ rtgui_region_data_t * oldData; /* Old data for newReg */ int prevBand; /* Index of start of * previous band in newReg */ int curBand; /* Index of start of current * band in newReg */ rtgui_rect_t * r1BandEnd; /* End of current band in r1 */ rtgui_rect_t * r2BandEnd; /* End of current band in r2 */ short top; /* Top of non-overlapping band */ short bot; /* Bottom of non-overlapping band*/ int r1y1; /* Temps for r1->y1 and r2->y1 */ int r2y1; int newSize; int numRects; /* * Break any region computed from a broken region */ if (PIXREGION_NAR (reg1) || PIXREGION_NAR(reg2)) return rtgui_break (newReg); /* * Initialization: * set r1, r2, r1End and r2End 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); newSize = PIXREGION_NUM_RECTS(reg1); r1End = r1 + newSize; numRects = PIXREGION_NUM_RECTS(reg2); r2 = PIXREGION_RECTS(reg2); r2End = r2 + numRects; RT_ASSERT(r1 != r1End); RT_ASSERT(r2 != r2End); oldData = (rtgui_region_data_t *)RT_NULL; if (((newReg == reg1) && (newSize > 1)) || ((newReg == reg2) && (numRects > 1))) { oldData = newReg->data; newReg->data = &rtgui_region_emptydata; } /* guess at new size */ if (numRects > newSize) newSize = numRects; newSize <<= 1; if (!newReg->data) newReg->data = &rtgui_region_emptydata; else if (newReg->data->size) newReg->data->numRects = 0; if (newSize > newReg->data->size) if (!rtgui_rect_alloc(newReg, newSize)) return RTGUI_REGION_STATUS_FAILURE; /* * Initialize ybot. * In the upcoRTGUI_MINg 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 = RTGUI_MIN(r1->y1, r2->y1); /* * prevBand serves to mark the start of the previous band so rectangles * can be coalesced into larger rectangles. qv. rtgui_coalesce, above. * In the beginning, there is no previous band, so prevBand == curBand * (curBand is set later on, of course, but the first band will always * start at index 0). prevBand and curBand must be indices because of * the possible expansion, and resultant moving, of the new region's * array of rectangles. */ prevBand = 0; do { /* * This algorithm proceeds one source-band (as opposed to a * destination band, which is deterRTGUI_MINed by where the two regions * intersect) at a time. r1BandEnd and r2BandEnd serve to mark the * rectangle after the last one in the current band for their * respective regions. */ RT_ASSERT(r1 != r1End); RT_ASSERT(r2 != r2End); FindBand(r1, r1BandEnd, r1End, r1y1); FindBand(r2, r2BandEnd, r2End, 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 (appendNon1) { top = RTGUI_MAX(r1y1, ybot); bot = RTGUI_MIN(r1->y2, r2y1); if (top != bot) { curBand = newReg->data->numRects; rtgui_region_appendNonO(newReg, r1, r1BandEnd, top, bot); Coalesce(newReg, prevBand, curBand); } } ytop = r2y1; } else if (r2y1 < r1y1) { if (appendNon2) { top = RTGUI_MAX(r2y1, ybot); bot = RTGUI_MIN(r2->y2, r1y1); if (top != bot) { curBand = newReg->data->numRects; rtgui_region_appendNonO(newReg, r2, r2BandEnd, top, bot); Coalesce(newReg, prevBand, curBand); } } ytop = r1y1; } else { ytop = r1y1; } /* * Now see if we've hit an intersecting band. The two bands only * intersect if ybot > ytop */ ybot = RTGUI_MIN(r1->y2, r2->y2); if (ybot > ytop) { curBand = newReg->data->numRects; (* overlapFunc)(newReg, r1, r1BandEnd, r2, r2BandEnd, ytop, ybot, pOverlap); Coalesce(newReg, prevBand, curBand); } /* * If we've finished with a band (y2 == ybot) we skip forward * in the region to the next band. */ if (r1->y2 == ybot) r1 = r1BandEnd; if (r2->y2 == ybot) r2 = r2BandEnd; } while (r1 != r1End && r2 != r2End); /* * 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 != r1End) && appendNon1) { /* Do first nonOverlap1Func call, which may be able to coalesce */ FindBand(r1, r1BandEnd, r1End, r1y1); curBand = newReg->data->numRects; rtgui_region_appendNonO(newReg, r1, r1BandEnd, RTGUI_MAX(r1y1, ybot), r1->y2); Coalesce(newReg, prevBand, curBand); /* Just append the rest of the boxes */ AppendRegions(newReg, r1BandEnd, r1End); } else if ((r2 != r2End) && appendNon2) { /* Do first nonOverlap2Func call, which may be able to coalesce */ FindBand(r2, r2BandEnd, r2End, r2y1); curBand = newReg->data->numRects; rtgui_region_appendNonO(newReg, r2, r2BandEnd, RTGUI_MAX(r2y1, ybot), r2->y2); Coalesce(newReg, prevBand, curBand); /* Append rest of boxes */ AppendRegions(newReg, r2BandEnd, r2End); } if (oldData) rtgui_free(oldData); numRects = newReg->data->numRects; if (!numRects) { freeData(newReg); newReg->data = &rtgui_region_emptydata; } else if (numRects == 1) { newReg->extents = *PIXREGION_BOXPTR(newReg); freeData(newReg); newReg->data = (rtgui_region_data_t *)RT_NULL; } else { DOWNSIZE(newReg, numRects); } return RTGUI_REGION_STATUS_SUCCESS; } /*- *----------------------------------------------------------------------- * rtgui_set_extents -- * Reset the extents of a region to what they should be. Called by * rtgui_region_subtract and rtgui_region_intersect as they can't figure it out along the * way or do so easily, as rtgui_region_union can. * * Results: * None. * * Side Effects: * The region's 'extents' structure is overwritten. * *----------------------------------------------------------------------- */ static void rtgui_set_extents (rtgui_region_t *region) { rtgui_rect_t *box, *boxEnd; 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); boxEnd = PIXREGION_END(region); /* * Since box is the first rectangle in the region, it must have the * smallest y1 and since boxEnd is the last rectangle in the region, * it must have the largest y2, because of banding. Initialize x1 and * x2 from box and boxEnd, resp., as good things to initialize them * to... */ region->extents.x1 = box->x1; region->extents.y1 = box->y1; region->extents.x2 = boxEnd->x2; region->extents.y2 = boxEnd->y2; RT_ASSERT(region->extents.y1 < region->extents.y2); while (box <= boxEnd) { if (box->x1 < region->extents.x1) region->extents.x1 = box->x1; if (box->x2 > region->extents.x2) region->extents.x2 = box->x2; box++; }; RT_ASSERT(region->extents.x1 < region->extents.x2); } /*====================================================================== * Region Intersection *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_region_intersectO -- * Handle an overlapping band for rtgui_region_intersect. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * Rectangles may be added to the region. * *----------------------------------------------------------------------- */ /*ARGSUSED*/ static rtgui_region_status_t rtgui_region_intersectO ( rtgui_region_t *region, rtgui_rect_t *r1, rtgui_rect_t *r1End, rtgui_rect_t *r2, rtgui_rect_t *r2End, short y1, short y2, int *pOverlap) { int x1; int x2; rtgui_rect_t * pNextRect; pNextRect = PIXREGION_TOP(region); RT_ASSERT(y1 < y2); RT_ASSERT(r1 != r1End && r2 != r2End); do { x1 = RTGUI_MAX(r1->x1, r2->x1); x2 = RTGUI_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 RTGUI_REGION_STATUS_SUCCESS; } rtgui_region_status_t rtgui_region_intersect(rtgui_region_t *newReg, rtgui_region_t *reg1, rtgui_region_t *reg2) { good(reg1); good(reg2); good(newReg); /* check for trivial reject */ if (PIXREGION_NIL(reg1) || PIXREGION_NIL(reg2) || !EXTENTCHECK(®1->extents, ®2->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 = &rtgui_brokendata; return RTGUI_REGION_STATUS_FAILURE; } else newReg->data = &rtgui_region_emptydata; } else if (!reg1->data && !reg2->data) { /* Covers about 80% of cases that aren't trivially rejected */ newReg->extents.x1 = RTGUI_MAX(reg1->extents.x1, reg2->extents.x1); newReg->extents.y1 = RTGUI_MAX(reg1->extents.y1, reg2->extents.y1); newReg->extents.x2 = RTGUI_MIN(reg1->extents.x2, reg2->extents.x2); newReg->extents.y2 = RTGUI_MIN(reg1->extents.y2, reg2->extents.y2); freeData(newReg); newReg->data = (rtgui_region_data_t *)RT_NULL; } else if (!reg2->data && SUBSUMES(®2->extents, ®1->extents)) { return rtgui_region_copy(newReg, reg1); } else if (!reg1->data && SUBSUMES(®1->extents, ®2->extents)) { return rtgui_region_copy(newReg, reg2); } else if (reg1 == reg2) { return rtgui_region_copy(newReg, reg1); } else { /* General purpose intersection */ int overlap; /* result ignored */ if (!rtgui_op(newReg, reg1, reg2, rtgui_region_intersectO, RTGUI_REGION_STATUS_FAILURE, RTGUI_REGION_STATUS_FAILURE, &overlap)) return RTGUI_REGION_STATUS_FAILURE; rtgui_set_extents(newReg); } good(newReg); return(RTGUI_REGION_STATUS_SUCCESS); } rtgui_region_status_t rtgui_region_intersect_rect(rtgui_region_t *newReg, rtgui_region_t *reg1, rtgui_rect_t *rect) { rtgui_region_t region; region.data = RT_NULL; region.extents.x1 = rect->x1; region.extents.y1 = rect->y1; region.extents.x2 = rect->x2; region.extents.y2 = rect->y2; return rtgui_region_intersect(newReg, reg1, ®ion); } #define MERGERECT(r) \ { \ if (r->x1 <= x2) { \ /* Merge with current rectangle */ \ if (r->x1 < x2) *pOverlap = RTGUI_REGION_STATUS_SUCCESS; \ 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 *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_region_unionO -- * Handle an overlapping band for the union operation. Picks the * left-most rectangle each time and merges it into the region. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * region is overwritten. * pOverlap is set to RTGUI_REGION_STATUS_SUCCESS if any boxes overlap. * *----------------------------------------------------------------------- */ static rtgui_region_status_t rtgui_region_unionO ( rtgui_region_t *region, rtgui_rect_t *r1, rtgui_rect_t *r1End, rtgui_rect_t *r2, rtgui_rect_t *r2End, short y1, short y2, int *pOverlap) { rtgui_rect_t * pNextRect; int x1; /* left and right side of current union */ int x2; RT_ASSERT (y1 < y2); RT_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 RTGUI_REGION_STATUS_SUCCESS; } /* Convenience function for perforRTGUI_MINg union of region with a single rectangle */ rtgui_region_status_t rtgui_region_union_rect(rtgui_region_t *dest, rtgui_region_t *source, rtgui_rect_t* rect) { rtgui_region_t region; region.data = RT_NULL; region.extents.x1 = rect->x1; region.extents.y1 = rect->y1; region.extents.x2 = rect->x2; region.extents.y2 = rect->y2; return rtgui_region_union (dest, source, ®ion); } rtgui_region_status_t rtgui_region_union(rtgui_region_t *newReg, rtgui_region_t *reg1, rtgui_region_t *reg2) { int overlap; /* result ignored */ /* Return RTGUI_REGION_STATUS_SUCCESS 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 rtgui_region_copy(newReg, reg1); } /* * Region 1 is empty */ if (PIXREGION_NIL(reg1)) { if (PIXREGION_NAR(reg1)) return rtgui_break (newReg); if (newReg != reg2) return rtgui_region_copy(newReg, reg2); return RTGUI_REGION_STATUS_SUCCESS; } /* * Region 2 is empty */ if (PIXREGION_NIL(reg2)) { if (PIXREGION_NAR(reg2)) return rtgui_break (newReg); if (newReg != reg1) return rtgui_region_copy(newReg, reg1); return RTGUI_REGION_STATUS_SUCCESS; } /* * Region 1 completely subsumes region 2 */ if (!reg1->data && SUBSUMES(®1->extents, ®2->extents)) { if (newReg != reg1) return rtgui_region_copy(newReg, reg1); return RTGUI_REGION_STATUS_SUCCESS; } /* * Region 2 completely subsumes region 1 */ if (!reg2->data && SUBSUMES(®2->extents, ®1->extents)) { if (newReg != reg2) return rtgui_region_copy(newReg, reg2); return RTGUI_REGION_STATUS_SUCCESS; } if (!rtgui_op(newReg, reg1, reg2, rtgui_region_unionO, RTGUI_REGION_STATUS_SUCCESS, RTGUI_REGION_STATUS_SUCCESS, &overlap)) return RTGUI_REGION_STATUS_FAILURE; newReg->extents.x1 = RTGUI_MIN(reg1->extents.x1, reg2->extents.x1); newReg->extents.y1 = RTGUI_MIN(reg1->extents.y1, reg2->extents.y1); newReg->extents.x2 = RTGUI_MAX(reg1->extents.x2, reg2->extents.x2); newReg->extents.y2 = RTGUI_MAX(reg1->extents.y2, reg2->extents.y2); good(newReg); return RTGUI_REGION_STATUS_SUCCESS; } /*====================================================================== * Batch Rectangle Union *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_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 rtgui_region_validate to ensure that a valid region is constructed. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * dstrgn is modified if rgn has rectangles. * */ rtgui_region_status_t rtgui_region_append(rtgui_region_t *dstrgn, rtgui_region_t *rgn) { int numRects, dnumRects, size; rtgui_rect_t *new, *old; int prepend; if (PIXREGION_NAR(rgn)) return rtgui_break (dstrgn); if (!rgn->data && (dstrgn->data == &rtgui_region_emptydata)) { dstrgn->extents = rgn->extents; dstrgn->data = (rtgui_region_data_t *)RT_NULL; return RTGUI_REGION_STATUS_SUCCESS; } numRects = PIXREGION_NUM_RECTS(rgn); if (!numRects) return RTGUI_REGION_STATUS_SUCCESS; prepend = RTGUI_REGION_STATUS_FAILURE; 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) { rtgui_rect_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 = RTGUI_REGION_STATUS_SUCCESS; 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 rt_memmove((char *)new,(char *)PIXREGION_BOXPTR(dstrgn), dnumRects * sizeof(rtgui_rect_t)); new = PIXREGION_BOXPTR(dstrgn); } else new = PIXREGION_BOXPTR(dstrgn) + dnumRects; if (numRects == 1) *new = *old; else rt_memmove((char *)new, (char *)old, numRects * sizeof(rtgui_rect_t)); dstrgn->data->numRects += numRects; return RTGUI_REGION_STATUS_SUCCESS; } #define ExchangeRects(a, b) \ { \ rtgui_rect_t t; \ t = rects[a]; \ rects[a] = rects[b]; \ rects[b] = t; \ } static void QuickSortRects(rtgui_rect_t rects[], int numRects) { int y1; int x1; int i, j; rtgui_rect_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 */ ExchangeRects(0, j); /* Recurse */ if (numRects-j-1 > 1) QuickSortRects(&rects[j+1], numRects-j-1); numRects = j; } while (numRects > 1); } /*- *----------------------------------------------------------------------- * rtgui_region_validate -- * * Take a ``region'' which is a non-y-x-banded random collection of * rectangles, and compute a nice region which is the union of all the * rectangles. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * The passed-in ``region'' may be modified. * pOverlap set to RTGUI_REGION_STATUS_SUCCESS if any retangles overlapped, else RTGUI_REGION_STATUS_FAILURE; * * Strategy: * Step 1. Sort the rectangles into ascending order with primary key y1 * and secondary key x1. * * Step 2. Split the rectangles into the RTGUI_MINimum number of proper y-x * banded regions. This may require horizontally merging * rectangles, and vertically coalescing bands. With any luck, * this step in an identity transformation (ala the Box widget), * or a coalescing into 1 box (ala Menus). * * Step 3. Merge the separate regions down to a single region by calling * rtgui_region_union. Maximize the work each rtgui_region_union call does by using * a binary merge. * *----------------------------------------------------------------------- */ rtgui_region_status_t rtgui_region_validate(rtgui_region_t * badreg, int *pOverlap) { /* Descriptor for regions under construction in Step 2. */ typedef struct { rtgui_region_t reg; int prevBand; int curBand; } RegionInfo; int numRects; /* Original numRects for badreg */ RegionInfo *ri; /* Array of current regions */ int numRI; /* Number of entries used in ri */ int sizeRI; /* Number of entries available in ri */ int i; /* Index into rects */ int j; /* Index into ri */ RegionInfo *rit; /* &ri[j] */ rtgui_region_t * reg; /* ri[j].reg */ rtgui_rect_t * box; /* Current box in rects */ rtgui_rect_t * riBox; /* Last box in ri[j].reg */ rtgui_region_t * hreg; /* ri[j_half].reg */ rtgui_region_status_t ret = RTGUI_REGION_STATUS_SUCCESS; *pOverlap = RTGUI_REGION_STATUS_FAILURE; if (!badreg->data) { good(badreg); return RTGUI_REGION_STATUS_SUCCESS; } numRects = badreg->data->numRects; if (!numRects) { if (PIXREGION_NAR(badreg)) return RTGUI_REGION_STATUS_FAILURE; good(badreg); return RTGUI_REGION_STATUS_SUCCESS; } if (badreg->extents.x1 < badreg->extents.x2) { if ((numRects) == 1) { freeData(badreg); badreg->data = (rtgui_region_data_t *) RT_NULL; } else { DOWNSIZE(badreg, numRects); } good(badreg); return RTGUI_REGION_STATUS_SUCCESS; } /* Step 1: Sort the rects array into ascending (y1, x1) order */ QuickSortRects(PIXREGION_BOXPTR(badreg), numRects); /* Step 2: Scatter the sorted array into the RTGUI_MINimum number of regions */ /* Set up the first region to be the first rectangle in badreg */ /* Note that step 2 code will never overflow the ri[0].reg rects array */ ri = (RegionInfo *) rtgui_malloc(4 * sizeof(RegionInfo)); if (!ri) return rtgui_break (badreg); sizeRI = 4; numRI = 1; ri[0].prevBand = 0; ri[0].curBand = 0; ri[0].reg = *badreg; box = PIXREGION_BOXPTR(&ri[0].reg); ri[0].reg.extents = *box; ri[0].reg.data->numRects = 1; /* Now scatter rectangles into the RTGUI_MINimum set of valid regions. If the next rectangle to be added to a region would force an existing rectangle in the region to be split up in order to maintain y-x banding, just forget it. Try the next region. If it doesn't fit cleanly into any region, make a new one. */ for (i = numRects; --i > 0;) { box++; /* Look for a region to append box to */ for (j = numRI, rit = ri; --j >= 0; rit++) { reg = &rit->reg; riBox = PIXREGION_END(reg); if (box->y1 == riBox->y1 && box->y2 == riBox->y2) { /* box is in same band as riBox. Merge or append it */ if (box->x1 <= riBox->x2) { /* Merge it with riBox */ if (box->x1 < riBox->x2) *pOverlap = RTGUI_REGION_STATUS_SUCCESS; if (box->x2 > riBox->x2) riBox->x2 = box->x2; } else { RECTALLOC_BAIL(reg, 1, bail); *PIXREGION_TOP(reg) = *box; reg->data->numRects++; } goto NextRect; /* So sue me */ } else if (box->y1 >= riBox->y2) { /* Put box into new band */ if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; if (reg->extents.x1 > box->x1) reg->extents.x1 = box->x1; Coalesce(reg, rit->prevBand, rit->curBand); rit->curBand = reg->data->numRects; RECTALLOC_BAIL(reg, 1, bail); *PIXREGION_TOP(reg) = *box; reg->data->numRects++; goto NextRect; } /* Well, this region was inappropriate. Try the next one. */ } /* for j */ /* Uh-oh. No regions were appropriate. Create a new one. */ if (sizeRI == numRI) { /* Oops, allocate space for new region information */ sizeRI <<= 1; rit = (RegionInfo *) rt_realloc(ri, sizeRI * sizeof(RegionInfo)); if (!rit) goto bail; ri = rit; rit = &ri[numRI]; } numRI++; rit->prevBand = 0; rit->curBand = 0; rit->reg.extents = *box; rit->reg.data = (rtgui_region_data_t *)RT_NULL; if (!rtgui_rect_alloc(&rit->reg, (i+numRI) / numRI)) /* MUST force allocation */ goto bail; NextRect: ; } /* for i */ /* Make a final pass over each region in order to Coalesce and set extents.x2 and extents.y2 */ for (j = numRI, rit = ri; --j >= 0; rit++) { reg = &rit->reg; riBox = PIXREGION_END(reg); reg->extents.y2 = riBox->y2; if (reg->extents.x2 < riBox->x2) reg->extents.x2 = riBox->x2; Coalesce(reg, rit->prevBand, rit->curBand); if (reg->data->numRects == 1) /* keep unions happy below */ { freeData(reg); reg->data = (rtgui_region_data_t *)RT_NULL; } } /* Step 3: Union all regions into a single region */ while (numRI > 1) { int half = numRI/2; for (j = numRI & 1; j < (half + (numRI & 1)); j++) { reg = &ri[j].reg; hreg = &ri[j+half].reg; if (!rtgui_op(reg, reg, hreg, rtgui_region_unionO, RTGUI_REGION_STATUS_SUCCESS, RTGUI_REGION_STATUS_SUCCESS, pOverlap)) ret = RTGUI_REGION_STATUS_FAILURE; if (hreg->extents.x1 < reg->extents.x1) reg->extents.x1 = hreg->extents.x1; if (hreg->extents.y1 < reg->extents.y1) reg->extents.y1 = hreg->extents.y1; if (hreg->extents.x2 > reg->extents.x2) reg->extents.x2 = hreg->extents.x2; if (hreg->extents.y2 > reg->extents.y2) reg->extents.y2 = hreg->extents.y2; freeData(hreg); } numRI -= half; } *badreg = ri[0].reg; rtgui_free(ri); good(badreg); return ret; bail: for (i = 0; i < numRI; i++) freeData(&ri[i].reg); rtgui_free (ri); return rtgui_break (badreg); } /*====================================================================== * Region Subtraction *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_region_subtractO -- * Overlapping band subtraction. x1 is the left-most point not yet * checked. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * region may have rectangles added to it. * *----------------------------------------------------------------------- */ /*ARGSUSED*/ static rtgui_region_status_t rtgui_region_subtractO ( rtgui_region_t *region, rtgui_rect_t *r1, rtgui_rect_t *r1End, rtgui_rect_t *r2, rtgui_rect_t *r2End, short y1, short y2, int *pOverlap) { rtgui_rect_t * pNextRect; int x1; x1 = r1->x1; RT_ASSERT(y1x2 <= x1) { /* * Subtrahend entirely to left of minuend: go to next subtrahend. */ r2++; } else if (r2->x1 <= x1) { /* * Subtrahend preceeds RTGUI_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 RTGUI_MINuend. */ r1++; if (r1 != r1End) 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. */ RT_ASSERT(x1x1); NEWRECT(region, pNextRect, x1, y1, r2->x1, y2); x1 = r2->x2; if (x1 >= r1->x2) { /* * Minuend used up: advance to new... */ r1++; if (r1 != r1End) x1 = r1->x1; } else { /* * Subtrahend used up */ r2++; } } else { /* * Minuend used up: add any remaining piece before advancing. */ if (r1->x2 > x1) NEWRECT(region, pNextRect, x1, y1, r1->x2, y2); r1++; if (r1 != r1End) x1 = r1->x1; } } while ((r1 != r1End) && (r2 != r2End)); /* * Add remaining minuend rectangles to region. */ while (r1 != r1End) { RT_ASSERT(x1x2); NEWRECT(region, pNextRect, x1, y1, r1->x2, y2); r1++; if (r1 != r1End) x1 = r1->x1; } return RTGUI_REGION_STATUS_SUCCESS; } /*- *----------------------------------------------------------------------- * rtgui_region_subtract -- * Subtract regS from regM and leave the result in regD. * S stands for subtrahend, M for minuend and D for difference. * * Results: * RTGUI_REGION_STATUS_SUCCESS if successful. * * Side Effects: * regD is overwritten. * *----------------------------------------------------------------------- */ rtgui_region_status_t rtgui_region_subtract(rtgui_region_t *regD, rtgui_region_t *regM, rtgui_region_t *regS) { int overlap; /* result ignored */ good(regM); good(regS); good(regD); /* check for trivial rejects */ if (PIXREGION_NIL(regM) || PIXREGION_NIL(regS) || !EXTENTCHECK(®M->extents, ®S->extents)) { if (PIXREGION_NAR (regS)) return rtgui_break (regD); return rtgui_region_copy(regD, regM); } else if (regM == regS) { freeData(regD); regD->extents.x2 = regD->extents.x1; regD->extents.y2 = regD->extents.y1; regD->data = &rtgui_region_emptydata; return RTGUI_REGION_STATUS_SUCCESS; } /* Add those rectangles in region 1 that aren't in region 2, do yucky substraction for overlaps, and just throw away rectangles in region 2 that aren't in region 1 */ if (!rtgui_op(regD, regM, regS, rtgui_region_subtractO, RTGUI_REGION_STATUS_SUCCESS, RTGUI_REGION_STATUS_FAILURE, &overlap)) return RTGUI_REGION_STATUS_FAILURE; /* * Can't alter RegD's extents before we call rtgui_op because * it might be one of the source regions and rtgui_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 exaRTGUI_MINe fewer rectangles. */ rtgui_set_extents(regD); good(regD); return RTGUI_REGION_STATUS_SUCCESS; } rtgui_region_status_t rtgui_region_subtract_rect (rtgui_region_t *regD, rtgui_region_t *regM, rtgui_rect_t* rect) { rtgui_region_t region; region.data = RT_NULL; region.extents.x1 = rect->x1; region.extents.y1 = rect->y1; region.extents.x2 = rect->x2; region.extents.y2 = rect->y2; return rtgui_region_subtract(regD, regM, ®ion); } /*====================================================================== * Region Inversion *====================================================================*/ /*- *----------------------------------------------------------------------- * rtgui_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: * RTGUI_REGION_STATUS_SUCCESS. * * Side Effects: * newReg is overwritten. * *----------------------------------------------------------------------- */ rtgui_region_status_t rtgui_region_inverse(rtgui_region_t *newReg, /* Destination region */ rtgui_region_t *reg1, /* Region to invert */ rtgui_rect_t *invRect) /* Bounding box for inversion */ { rtgui_region_t invReg; /* Quick and dirty region made from the * bounding box */ int overlap; /* result ignored */ good(reg1); good(newReg); /* check for trivial rejects */ if (PIXREGION_NIL(reg1) || !EXTENTCHECK(invRect, ®1->extents)) { if (PIXREGION_NAR(reg1)) return rtgui_break (newReg); newReg->extents = *invRect; freeData(newReg); newReg->data = (rtgui_region_data_t *)RT_NULL; return RTGUI_REGION_STATUS_SUCCESS; } /* Add those rectangles in region 1 that aren't in region 2, do yucky substraction for overlaps, and just throw away rectangles in region 2 that aren't in region 1 */ invReg.extents = *invRect; invReg.data = (rtgui_region_data_t *)RT_NULL; if (!rtgui_op(newReg, &invReg, reg1, rtgui_region_subtractO, RTGUI_REGION_STATUS_SUCCESS, RTGUI_REGION_STATUS_FAILURE, &overlap)) return RTGUI_REGION_STATUS_FAILURE; /* * Can't alter newReg's extents before we call rtgui_op because * it might be one of the source regions and rtgui_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 exaRTGUI_MINe fewer rectangles. */ rtgui_set_extents(newReg); good(newReg); return RTGUI_REGION_STATUS_SUCCESS; } /* * RectIn(region, rect) * This routine takes a pointer to a region and a pointer to a box * and deterRTGUI_MINes 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, partOut is set RTGUI_REGION_STATUS_SUCCESS. Any time a rectangle in * the region covers part of the box, partIn is set RTGUI_REGION_STATUS_SUCCESS. The process ends * when either the box has been completely covered (we reached a band that * doesn't overlap the box, partIn is RTGUI_REGION_STATUS_SUCCESS and partOut is false), the * box has been partially covered (partIn == partOut == RTGUI_REGION_STATUS_SUCCESS -- 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 partIn is false) */ int rtgui_region_contains_rectangle(rtgui_region_t *region, rtgui_rect_t *prect) { int x; int y; rtgui_rect_t * pbox; rtgui_rect_t * pboxEnd; int partIn, partOut; int numRects; good(region); numRects = PIXREGION_NUM_RECTS(region); /* useful optimization */ if (!numRects || !EXTENTCHECK(®ion->extents, prect)) return(RTGUI_REGION_OUT); if (numRects == 1) { /* We know that it must be rgnIN or rgnPART */ if (SUBSUMES(®ion->extents, prect)) return(RTGUI_REGION_IN); else return(RTGUI_REGION_PART); } partOut = RTGUI_REGION_STATUS_FAILURE; partIn = RTGUI_REGION_STATUS_FAILURE; /* (x,y) starts at upper left of rect, moving to the right and down */ x = prect->x1; y = prect->y1; /* can stop when both partOut and partIn are RTGUI_REGION_STATUS_SUCCESS, or we reach prect->y2 */ for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects; pbox != pboxEnd; pbox++) { if (pbox->y2 <= y) continue; /* getting up to speed or skipping remainder of band */ if (pbox->y1 > y) { partOut = RTGUI_REGION_STATUS_SUCCESS; /* missed part of rectangle above */ if (partIn || (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) { partOut = RTGUI_REGION_STATUS_SUCCESS; /* missed part of rectangle to left */ if (partIn) break; } if (pbox->x1 < prect->x2) { partIn = RTGUI_REGION_STATUS_SUCCESS; /* definitely overlap */ if (partOut) 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. partIn will have been set true * by now... */ partOut = RTGUI_REGION_STATUS_SUCCESS; break; } } return(partIn ? ((y < prect->y2) ? RTGUI_REGION_PART : RTGUI_REGION_IN) : RTGUI_REGION_OUT); } /* rtgui_region_translate (region, x, y) translates in place */ void rtgui_region_translate (rtgui_region_t *region, int x, int y) { int x1, x2, y1, y2; int nbox; rtgui_rect_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 - RTGUI_SHRT_MIN)|(y1 - RTGUI_SHRT_MIN)|(RTGUI_SHRT_MAX - x2)|(RTGUI_SHRT_MAX - y2)) >= 0) { nbox = region->data->numRects; if (region->data && nbox) { for (pbox = PIXREGION_BOXPTR(region); nbox--; pbox++) { pbox->x1 += x; pbox->y1 += y; pbox->x2 += x; pbox->y2 += y; } } return; } if (((x2 - RTGUI_SHRT_MIN)|(y2 - RTGUI_SHRT_MIN)|(RTGUI_SHRT_MAX - x1)|(RTGUI_SHRT_MAX - y1)) <= 0) { region->extents.x2 = region->extents.x1; region->extents.y2 = region->extents.y1; freeData(region); region->data = &rtgui_region_emptydata; return; } if (x1 < RTGUI_SHRT_MIN) region->extents.x1 = RTGUI_SHRT_MIN; else if (x2 > RTGUI_SHRT_MAX) region->extents.x2 = RTGUI_SHRT_MAX; if (y1 < RTGUI_SHRT_MIN) region->extents.y1 = RTGUI_SHRT_MIN; else if (y2 > RTGUI_SHRT_MAX) region->extents.y2 = RTGUI_SHRT_MAX; nbox = region->data->numRects; if (region->data && nbox) { rtgui_rect_t * pboxout; for (pboxout = pbox = PIXREGION_BOXPTR(region); nbox--; pbox++) { pboxout->x1 = x1 = pbox->x1 + x; pboxout->y1 = y1 = pbox->y1 + y; pboxout->x2 = x2 = pbox->x2 + x; pboxout->y2 = y2 = pbox->y2 + y; if (((x2 - RTGUI_SHRT_MIN)|(y2 - RTGUI_SHRT_MIN)| (RTGUI_SHRT_MAX - x1)|(RTGUI_SHRT_MAX - y1)) <= 0) { region->data->numRects--; continue; } if (x1 < RTGUI_SHRT_MIN) pboxout->x1 = RTGUI_SHRT_MIN; else if (x2 > RTGUI_SHRT_MAX) pboxout->x2 = RTGUI_SHRT_MAX; if (y1 < RTGUI_SHRT_MIN) pboxout->y1 = RTGUI_SHRT_MIN; else if (y2 > RTGUI_SHRT_MAX) pboxout->y2 = RTGUI_SHRT_MAX; pboxout++; } if (pboxout != pbox) { if (region->data->numRects == 1) { region->extents = *PIXREGION_BOXPTR(region); freeData(region); region->data = (rtgui_region_data_t *)RT_NULL; } else rtgui_set_extents(region); } } } void rtgui_region_reset(rtgui_region_t *region, rtgui_rect_t* rect) { good(region); freeData(region); rtgui_region_init_with_extents(region, rect); } /* box is "return" value */ int rtgui_region_contains_point(rtgui_region_t * region, int x, int y, rtgui_rect_t * box) { rtgui_rect_t *pbox, *pboxEnd; int numRects; good(region); numRects = PIXREGION_NUM_RECTS(region); if (!numRects || !INBOX(®ion->extents, x, y)) return -RT_ERROR; if (numRects == 1) { *box = region->extents; return RT_EOK; } for (pbox = PIXREGION_BOXPTR(region), pboxEnd = pbox + numRects; pbox != pboxEnd; pbox++) { if (y >= pbox->y2) continue; /* not there yet */ if ((y < pbox->y1) || (x < pbox->x1)) break; /* missed it */ if (x >= pbox->x2) continue; /* not there yet */ *box = *pbox; return RT_EOK; } return -RT_ERROR; } int rtgui_region_not_empty(rtgui_region_t * region) { good(region); return(!PIXREGION_NIL(region)); } void rtgui_region_empty(rtgui_region_t * region) { good(region); freeData(region); region->extents = rtgui_empty_rect; region->data = &rtgui_region_emptydata; } rtgui_rect_t *rtgui_region_extents(rtgui_region_t * region) { good(region); return(®ion->extents); } #define ExchangeSpans(a, b) \ { \ rtgui_point_t tpt; \ int tw; \ \ tpt = spans[a]; spans[a] = spans[b]; spans[b] = tpt; \ tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ } /* ||| I should apply the merge sort code to rectangle sorting above, and see if mapping time can be improved. But right now I've been at work 12 hours, so forget it. */ static void QuickSortSpans( rtgui_point_t spans[], int widths[], int numSpans) { int y; int i, j, m; rtgui_point_t *r; /* Always called with numSpans > 1 */ /* Sorts only by y, doesn't bother to sort by x */ do { if (numSpans < 9) { /* Do insertion sort */ int yprev; yprev = spans[0].y; i = 1; do { /* while i != numSpans */ y = spans[i].y; if (yprev > y) { /* spans[i] is out of order. Move into proper location. */ rtgui_point_t tpt; int tw, k; for (j = 0; y >= spans[j].y; j++) {} tpt = spans[i]; tw = widths[i]; for (k = i; k != j; k--) { spans[k] = spans[k-1]; widths[k] = widths[k-1]; } spans[j] = tpt; widths[j] = tw; y = spans[i].y; } /* if out of order */ yprev = y; i++; } while (i != numSpans); return; } /* Choose partition element, stick in location 0 */ m = numSpans / 2; if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); if (spans[m].y > spans[numSpans-1].y) ExchangeSpans(m, numSpans-1); if (spans[m].y > spans[0].y) ExchangeSpans(m, 0); y = spans[0].y; /* Partition array */ i = 0; j = numSpans; do { r = &(spans[i]); do { r++; i++; } while (i != numSpans && r->y < y); r = &(spans[j]); do { r--; j--; } while (y < r->y); if (i < j) ExchangeSpans(i, j); } while (i < j); /* Move partition element back to middle */ ExchangeSpans(0, j); /* Recurse */ if (numSpans-j-1 > 1) QuickSortSpans(&spans[j+1], &widths[j+1], numSpans-j-1); numSpans = j; } while (numSpans > 1); } void rtgui_region_dump(rtgui_region_t* region) { int num; int i; rtgui_rect_t * rects; num = PIXREGION_NUM_RECTS(region); rects = PIXREGION_RECTS(region); rt_kprintf("extents: (%d,%d) (%d,%d)\n", region->extents.x1, region->extents.y1, region->extents.x2, region->extents.y2); for (i = 0; i < num; i++) { rt_kprintf("box[%d]: (%d,%d) (%d,%d)\n", i, rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2); } } int rtgui_region_is_flat(rtgui_region_t* region) { int num; num = PIXREGION_NUM_RECTS(region); if (num == 1) return RT_EOK; return -RT_ERROR; } void rtgui_rect_moveto(rtgui_rect_t *rect, int x, int y) { rect->x1 += x; rect->x2 += x; rect->y1 += y; rect->y2 += y; } void rtgui_rect_moveto_align(rtgui_rect_t *rect, rtgui_rect_t *to, int align) { int dw, dh; dw = 0; dh = 0; /* get delta width and height */ dw = rtgui_rect_width(*rect) - rtgui_rect_width(*to); dh = rtgui_rect_height(*rect) - rtgui_rect_height(*to); if (dw < 0) dw = 0; if (dh < 0) dh = 0; /* move to insider of rect */ rtgui_rect_moveto(to, rect->x1, rect->y1); /* limited the destination rect to source rect */ if (dw == 0) to->x2 = rect->x2; if (dh == 0) to->y2 = rect->y2; /* align to right */ if (align & RTGUI_ALIGN_RIGHT) { to->x1 += dw; to->x2 += dw; } /* align to bottom */ if (align & RTGUI_ALIGN_BOTTOM) { to->y1 += dh; to->y2 += dh; } /* align to center horizontal */ if (align & RTGUI_ALIGN_CENTER_HORIZONTAL) { to->x1 += dw >> 1; to->x2 += dw >> 1; } /* align to center vertical */ if (align & RTGUI_ALIGN_CENTER_VERTICAL) { to->y1 += dh >> 1; to->y2 += dh >> 1; } } void rtgui_rect_inflate(rtgui_rect_t *rect, int d) { rect->x1 -= d; rect->x2 += d; rect->y1 -= d; rect->y2 += d; } /* put the intersect of src rect and dest rect to dest */ void rtgui_rect_intersect(rtgui_rect_t *src, rtgui_rect_t *dest) { if (dest->x1 < src->x1) dest->x1 = src->x1; if (dest->y1 < src->y1) dest->y1 = src->y1; if (dest->x2 > src->x2) dest->x2 = src->x2; if (dest->y2 > src->y2) dest->y2 = src->y2; } int rtgui_rect_contains_point(const rtgui_rect_t *rect, int x, int y) { if (INBOX(rect, x, y)) return RT_EOK; return -RT_ERROR; } int rtgui_rect_is_intersect(const rtgui_rect_t *rect1, const rtgui_rect_t *rect2) { if (INBOX(rect1, rect2->x1, rect2->y1) || INBOX(rect1, rect2->x1, rect2->y2) || INBOX(rect1, rect2->x2, rect2->y1) || INBOX(rect1, rect2->x2, rect2->y2)) { return RT_EOK; } else if (INBOX(rect2, rect1->x1, rect1->y1) || INBOX(rect2, rect1->x1, rect1->y2) || INBOX(rect2, rect1->x2, rect1->y1) || INBOX(rect2, rect1->x2, rect1->y2)) { return RT_EOK; } return -RT_ERROR; }