Mercurial > ecos
diff packages/services/gfx/mw/current/src/engine/devpoly.c @ 208:e0c0827131d1 ecos
Merge from eCos master repository on 2002-05-20-20:11:54-BST
| author | jlarmour |
|---|---|
| date | Mon, 20 May 2002 22:19:26 +0000 |
| parents | |
| children |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/packages/services/gfx/mw/current/src/engine/devpoly.c @@ -0,0 +1,636 @@ +#include <stdio.h> +#include <stdlib.h> +#include "device.h" +/* + * Microwindows polygon outline and fill routines. + * Copyright (c) 1999, 2000, 2001 Greg Haerr <greg@censoft.com> + * Portions Copyright (c) 1991 David I. Bell + * + * There are currently three implementations of the polygon + * fill routine. The version from X11 most properly + * fills polygons that must also be outlined as well. All are + * controlled with #if directive in this file. + */ + +/* extern definitions*/ +void drawpoint(PSD psd,MWCOORD x, MWCOORD y); +void drawrow(PSD psd,MWCOORD x1,MWCOORD x2,MWCOORD y); +extern int gr_mode; /* drawing mode */ + +/* Draw a polygon in the foreground color, applying clipping if necessary. + * The polygon is only closed if the first point is repeated at the end. + * Some care is taken to plot the endpoints correctly if the current + * drawing mode is XOR. However, internal crossings are not handled + * correctly. + */ +void +GdPoly(PSD psd, int count, MWPOINT *points) +{ + MWCOORD firstx; + MWCOORD firsty; + MWBOOL didline; + + if (count < 2) + return; + firstx = points->x; + firsty = points->y; + didline = FALSE; + + while (count-- > 1) { + if (didline && (gr_mode == MWMODE_XOR)) + drawpoint(psd, points->x, points->y); + /* note: change to drawline*/ + GdLine(psd, points[0].x, points[0].y, points[1].x, points[1].y, TRUE); + points++; + didline = TRUE; + } + if (gr_mode == MWMODE_XOR) { + points--; + if (points->x == firstx && points->y == firsty) + drawpoint(psd, points->x, points->y); + } + GdFixCursor(psd); +} + +#if 1 /* improved convex polygon fill routine*/ +/*********************************************************** +Copyright (c) 1987 X Consortium + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN +AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + +Except as contained in this notice, the name of the X Consortium shall not be +used in advertising or otherwise to promote the sale, use or other dealings +in this Software without prior written authorization from the X Consortium. + + +Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts. + + All Rights Reserved + +Permission to use, copy, modify, and distribute this software and its +documentation for any purpose and without fee is hereby granted, +provided that the above copyright notice appear in all copies and that +both that copyright notice and this permission notice appear in +supporting documentation, and that the name of Digital not be +used in advertising or publicity pertaining to distribution of the +software without specific, written prior permission. + +DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING +ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL +DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR +ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, +WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, +ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +SOFTWARE. +******************************************************************/ + +/* + * Written by Brian Kelleher; Dec. 1985. + * Adapted for Microwindows Sep 2001 by Greg Haerr <greg@censoft.com> + * + * Fill a convex polygon in the fg color, with clipping. + * If the given polygon + * is not convex, then the result is undefined. + * The algorithm is to order the edges from smallest + * y to largest by partitioning the array into a left + * edge list and a right edge list. The algorithm used + * to traverse each edge is an extension of Bresenham's + * line algorithm with y as the major axis. + * + * This file contains a few macros to help track + * the edge of a filled object. The object is assumed + * to be filled in scanline order, and thus the + * algorithm used is an extension of Bresenham's line + * drawing algorithm which assumes that y is always the + * major axis. + * + * In scan converting polygons, we want to choose those pixels + * which are inside the polygon. Thus, we add .5 to the starting + * x coordinate for both left and right edges. Now we choose the + * first pixel which is inside the pgon for the left edge and the + * first pixel which is outside the pgon for the right edge. + * Draw the left pixel, but not the right. + * + * How to add .5 to the starting x coordinate: + * If the edge is moving to the right, then subtract dy from the + * error term from the general form of the algorithm. + * If the edge is moving to the left, then add dy to the error term. + * + * The reason for the difference between edges moving to the left + * and edges moving to the right is simple: If an edge is moving + * to the right, then we want the algorithm to flip immediately. + * If it is moving to the left, then we don't want it to flip until + * we traverse an entire pixel. + */ +#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \ + int dx; /* local storage */ \ +\ + /* \ + * if the edge is horizontal, then it is ignored \ + * and assumed not to be processed. Otherwise, do this stuff. \ + */ \ + if ((dy) != 0) { \ + xStart = (x1); \ + dx = (x2) - xStart; \ + if (dx < 0) { \ + m = dx / (dy); \ + m1 = m - 1; \ + incr1 = -2 * dx + 2 * (dy) * m1; \ + incr2 = -2 * dx + 2 * (dy) * m; \ + d = 2 * m * (dy) - 2 * dx - 2 * (dy); \ + } else { \ + m = dx / (dy); \ + m1 = m + 1; \ + incr1 = 2 * dx - 2 * (dy) * m1; \ + incr2 = 2 * dx - 2 * (dy) * m; \ + d = -2 * m * (dy) + 2 * dx; \ + } \ + } \ +} + +#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \ + if (m1 > 0) { \ + if (d > 0) { \ + minval += m1; \ + d += incr1; \ + } \ + else { \ + minval += m; \ + d += incr2; \ + } \ + } else {\ + if (d >= 0) { \ + minval += m1; \ + d += incr1; \ + } \ + else { \ + minval += m; \ + d += incr2; \ + } \ + } \ +} + +/* + * Find the index of the point with the smallest y. + */ +static int +getPolyYBounds(MWPOINT *pts, int n, int *by, int *ty) +{ + MWPOINT *ptMin; + int ymin, ymax; + MWPOINT *ptsStart = pts; + + ptMin = pts; + ymin = ymax = (pts++)->y; + + while (--n > 0) { + if (pts->y < ymin) + { + ptMin = pts; + ymin = pts->y; + } + if(pts->y > ymax) + ymax = pts->y; + + pts++; + } + + *by = ymin; + *ty = ymax; + return(ptMin-ptsStart); +} + +void +GdFillPoly(PSD psd, int count, MWPOINT *pointtable) +{ + MWCOORD xl = 0, xr = 0; /* x vals of left and right edges */ + int dl = 0, dr = 0; /* decision variables */ + int ml = 0, m1l = 0; /* left edge slope and slope+1 */ + int mr = 0, m1r = 0; /* right edge slope and slope+1 */ + int incr1l = 0, incr2l = 0; /* left edge error increments */ + int incr1r = 0, incr2r = 0; /* right edge error increments */ + int dy; /* delta y */ + MWCOORD y; /* current scanline */ + int left, right; /* indices to first endpoints */ + int i; /* loop counter */ + int nextleft, nextright; /* indices to second endpoints */ + MWPOINT *ptsOut, *FirstPoint;/* output buffer */ + MWCOORD *width, *FirstWidth;/* output buffer */ + int imin; /* index of smallest vertex (in y)*/ + int ymin; /* y-extents of polygon */ + int ymax; + + /* + * find leftx, bottomy, rightx, topy, and the index + * of bottomy. + */ + imin = getPolyYBounds(pointtable, count, &ymin, &ymax); + + dy = ymax - ymin + 1; + if ((count < 3) || (dy < 0)) + return; + ptsOut = FirstPoint = (MWPOINT *)ALLOCA(sizeof(MWPOINT) * dy); + width = FirstWidth = (MWCOORD *)ALLOCA(sizeof(MWCOORD) * dy); + if(!FirstPoint || !FirstWidth) + { + if (FirstWidth) FREEA(FirstWidth); + if (FirstPoint) FREEA(FirstPoint); + return; + } + + nextleft = nextright = imin; + y = pointtable[nextleft].y; + + /* + * loop through all edges of the polygon + */ + do { + /* + * add a left edge if we need to + */ + if (pointtable[nextleft].y == y) { + left = nextleft; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextleft++; + if (nextleft >= count) + nextleft = 0; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(pointtable[nextleft].y-pointtable[left].y, + pointtable[left].x,pointtable[nextleft].x, + xl, dl, ml, m1l, incr1l, incr2l); + } + + /* + * add a right edge if we need to + */ + if (pointtable[nextright].y == y) { + right = nextright; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextright--; + if (nextright < 0) + nextright = count-1; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(pointtable[nextright].y-pointtable[right].y, + pointtable[right].x,pointtable[nextright].x, + xr, dr, mr, m1r, incr1r, incr2r); + } + + /* + * generate scans to fill while we still have + * a right edge as well as a left edge. + */ + i = MWMIN(pointtable[nextleft].y, pointtable[nextright].y) - y; + /* in case we're called with non-convex polygon */ + if(i < 0) + { + FREEA(FirstWidth); + FREEA(FirstPoint); + return; + } + while (i-- > 0) + { + ptsOut->y = y; + + /* + * reverse the edges if necessary + */ + if (xl < xr) + { + *(width++) = xr - xl; + (ptsOut++)->x = xl; + } + else + { + *(width++) = xl - xr; + (ptsOut++)->x = xr; + } + y++; + + /* increment down the edges */ + BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l); + BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r); + } + } while (y != ymax); + + /* + * Finally, fill the spans + */ + i = ptsOut-FirstPoint; + ptsOut = FirstPoint; + width = FirstWidth; + while (--i >= 0) { + /* calc x extent from width*/ + int e = *width++ - 1; + if (e >= 0) { + drawrow(psd, ptsOut->x, ptsOut->x + e, ptsOut->y); + } + ++ptsOut; + } + + FREEA(FirstWidth); + FREEA(FirstPoint); + GdFixCursor(psd); +} +#endif + +#if 0 /* original convex only polygon fill routine*/ +/* + * Fill a polygon in the foreground color, applying clipping if necessary. + * The last point may be a duplicate of the first point, but this is + * not required. + * Note: this routine currently only correctly fills convex polygons. + */ + +/* Utility routine for filling polygons. Find the intersection point (if + * any) of a horizontal line with an arbitrary line, and extend the current + * minimum and maximum x values as needed to include the intersection point. + * Input parms: + * y row to check for intersection + * x1, y1 first endpoint + * x2, y2 second enpoint + * minxptr address of current minimum x + * maxxptr address of current maximum x + */ +static void +extendrow(MWCOORD y,MWCOORD x1,MWCOORD y1,MWCOORD x2,MWCOORD y2, + MWCOORD *minxptr,MWCOORD *maxxptr) +{ + MWCOORD x; /* x coordinate of intersection */ + typedef long NUM; + NUM num; /* numerator of fraction */ + + /* First make sure the specified line segment includes the specified + * row number. If not, then there is no intersection. + */ + if (((y < y1) || (y > y2)) && ((y < y2) || (y > y1))) + return; + + /* If a horizontal line, then check the two endpoints. */ + if (y1 == y2) { + if (*minxptr > x1) *minxptr = x1; + if (*minxptr > x2) *minxptr = x2; + if (*maxxptr < x1) *maxxptr = x1; + if (*maxxptr < x2) *maxxptr = x2; + return; + } + + /* If a vertical line, then check the x coordinate. */ + if (x1 == x2) { + if (*minxptr > x1) *minxptr = x1; + if (*maxxptr < x1) *maxxptr = x1; + return; + } + + /* An arbitrary line. Calculate the intersection point using the + * formula x = x1 + (y - y1) * (x2 - x1) / (y2 - y1). + */ + num = ((NUM) (y - y1)) * (x2 - x1); + x = x1 + num / (y2 - y1); + if (*minxptr > x) *minxptr = x; + if (*maxxptr < x) *maxxptr = x; +} + +void +GdFillPoly(PSD psd, int count, MWPOINT *points) +{ + MWPOINT *pp; /* current point */ + MWCOORD miny; /* minimum row */ + MWCOORD maxy; /* maximum row */ + MWCOORD minx; /* minimum column */ + MWCOORD maxx; /* maximum column */ + int i; /* counter */ + + if (count <= 0) + return; + + /* First determine the minimum and maximum rows for the polygon. */ + pp = points; + miny = pp->y; + maxy = pp->y; + for (i = count; i-- > 0; pp++) { + if (miny > pp->y) miny = pp->y; + if (maxy < pp->y) maxy = pp->y; + } + if (miny < 0) + miny = 0; + if (maxy >= psd->yvirtres) + maxy = psd->yvirtres - 1; + if (miny > maxy) + return; + + /* Now for each row, scan the list of points and determine the + * minimum and maximum x coordinate for each line, and plot the row. + * The last point connects with the first point automatically. + */ + for (; miny <= maxy; miny++) { + minx = MAX_MWCOORD; + maxx = MIN_MWCOORD; + pp = points; + for (i = count; --i > 0; pp++) + extendrow(miny, pp[0].x, pp[0].y, pp[1].x, pp[1].y, + &minx, &maxx); + extendrow(miny, pp[0].x, pp[0].y, points[0].x, points[0].y, + &minx, &maxx); + + if (minx <= maxx) + drawrow(psd, minx, maxx, miny); + } + GdFixCursor(psd); +} +#endif + +#if 0 /* irregular polygon fill, uses edge table, malloc, qsort*/ +/* + * Fill a polygon in the foreground color, applying clipping if necessary. + * The last point may be a duplicate of the first point, but this is + * not required. + * Note: this routine correctly draws convex, concave, regular, + * and irregular polygons. + */ +#define USE_FLOAT HAVEFLOAT /* set to use floating point*/ + +#define swap(a,b) do { a ^= b; b ^= a; a ^= b; } while (0) + +typedef struct { + int x1, y1, x2, y2; +#if USE_FLOAT + double x, m; +#else + int cx, fn, mn, d; +#endif +} edge_t; + +static int +edge_cmp(const void *lvp, const void *rvp) +{ + /* convert from void pointers to structure pointers */ + const edge_t *lp = (const edge_t *)lvp; + const edge_t *rp = (const edge_t *)rvp; + + /* if the minimum y values are different, sort on minimum y */ + if (lp->y1 != rp->y1) + return lp->y1 - rp->y1; + + /* if the current x values are different, sort on current x */ +#if USE_FLOAT + if (lp->x < rp->x) + return -1; + else if (lp->x > rp->x) + return +1; +#else + if (lp->cx != rp->cx) + return lp->cx - rp->cx; +#endif + + /* otherwise they are equal */ + return 0; +} + +void +GdFillPoly(PSD psd, int count, MWPOINT * pointtable) +{ + edge_t *get; /* global edge table */ + int nge = 0; /* num global edges */ + int cge = 0; /* cur global edge */ + + edge_t *aet; /* active edge table */ + int nae = 0; /* num active edges */ + + int i, y; + + if (count < 3) { + /* error, polygons require at least three edges (a triangle) */ + return; + } + get = (edge_t *) calloc(count, sizeof(edge_t)); + aet = (edge_t *) calloc(count, sizeof(edge_t)); + + if ((get == 0) || (aet == 0)) { + /* error, couldn't allocate one or both of the needed tables */ + if (get) + free(get); + if (aet) + free(aet); + return; + } + /* setup the global edge table */ + for (i = 0; i < count; ++i) { + get[nge].x1 = pointtable[i].x; + get[nge].y1 = pointtable[i].y; + get[nge].x2 = pointtable[(i + 1) % count].x; + get[nge].y2 = pointtable[(i + 1) % count].y; + if (get[nge].y1 != get[nge].y2) { + if (get[nge].y1 > get[nge].y2) { + swap(get[nge].x1, get[nge].x2); + swap(get[nge].y1, get[nge].y2); + } +#if USE_FLOAT + get[nge].x = get[nge].x1; + get[nge].m = get[nge].x2 - get[nge].x1; + get[nge].m /= get[nge].y2 - get[nge].y1; +#else + get[nge].cx = get[nge].x1; + get[nge].mn = get[nge].x2 - get[nge].x1; + get[nge].d = get[nge].y2 - get[nge].y1; + get[nge].fn = get[nge].mn / 2; +#endif + ++nge; + } + } + + qsort(get, nge, sizeof(get[0]), edge_cmp); + + /* start with the lowest y in the table */ + y = get[0].y1; + + do { + + /* add edges to the active table from the global table */ + while ((nge > 0) && (get[cge].y1 == y)) { + aet[nae] = get[cge++]; + --nge; + aet[nae++].y1 = 0; + } + + qsort(aet, nae, sizeof(aet[0]), edge_cmp); + + /* using odd parity, render alternating line segments */ + for (i = 1; i < nae; i += 2) { +#if USE_FLOAT + int l = (int)aet[i - 1].x; + int r = (int)aet[i].x; +#else + int l = (int)aet[i - 1].cx; + int r = (int)aet[i].cx; +#endif + if (r > l) + drawrow(psd, l, r - 1, y); + } + + /* prepare for the next scan line */ + ++y; + + /* remove inactive edges from the active edge table */ + /* or update the current x position of active edges */ + for (i = 0; i < nae; ++i) { + if (aet[i].y2 == y) + aet[i--] = aet[--nae]; + else { +#if USE_FLOAT + aet[i].x += aet[i].m; +#else + aet[i].fn += aet[i].mn; + if (aet[i].fn < 0) { + aet[i].cx += aet[i].fn / aet[i].d - 1; + aet[i].fn %= aet[i].d; + aet[i].fn += aet[i].d; + } + if (aet[i].fn >= aet[i].d) { + aet[i].cx += aet[i].fn / aet[i].d; + aet[i].fn %= aet[i].d; + } +#endif + } + } + + /* keep doing this while there are any edges left */ + } while ((nae > 0) || (nge > 0)); + + /* all done, free the edge tables */ + free(get); + free(aet); + + GdFixCursor(psd); +} +#endif
