devpoly.c

开放源码实时操作系统源码.

	}
        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