packages/services/gfx/mw/v2_0/src/engine/devpoly.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include "device.h"
   4 /*
   5  * Microwindows polygon outline and fill routines.
   6  * Copyright (c) 1999, 2000, 2001 Greg Haerr <greg@censoft.com>
   7  * Portions Copyright (c) 1991 David I. Bell
   8  *
   9  * There are currently three implementations of the polygon
  10  * fill routine.  The version from X11 most properly
  11  * fills polygons that must also be outlined as well. All are
  12  * controlled with #if directive in this file.
  13  */
  14
  15 /* extern definitions*/
  16 void drawpoint(PSD psd,MWCOORD x, MWCOORD y);
  17 void drawrow(PSD psd,MWCOORD x1,MWCOORD x2,MWCOORD y);
  18 extern int        gr_mode;            /* drawing mode */
  19
  20 /* Draw a polygon in the foreground color, applying clipping if necessary.
  21  * The polygon is only closed if the first point is repeated at the end.
  22  * Some care is taken to plot the endpoints correctly if the current
  23  * drawing mode is XOR.  However, internal crossings are not handled
  24  * correctly.
  25  */
  26 void
  27 GdPoly(PSD psd, int count, MWPOINT *points)
  28 {
  29   MWCOORD firstx;
  30   MWCOORD firsty;
  31   MWBOOL didline;
  32
  33   if (count < 2)
  34           return;
  35   firstx = points->x;
  36   firsty = points->y;
  37   didline = FALSE;
  38
  39   while (count-- > 1) {
  40         if (didline && (gr_mode == MWMODE_XOR))
  41                 drawpoint(psd, points->x, points->y);
  42         /* note: change to drawline*/
  43         GdLine(psd, points[0].x, points[0].y, points[1].x, points[1].y, TRUE);
  44         points++;
  45         didline = TRUE;
  46   }
  47   if (gr_mode == MWMODE_XOR) {
  48           points--;
  49           if (points->x == firstx && points->y == firsty)
  50                 drawpoint(psd, points->x, points->y);
  51   }
  52   GdFixCursor(psd);
  53 }
  54
  55 #if 1 /* improved convex polygon fill routine*/
  56 /***********************************************************
  57 Copyright (c) 1987  X Consortium
  58
  59 Permission is hereby granted, free of charge, to any person obtaining a copy
  60 of this software and associated documentation files (the "Software"), to deal
  61 in the Software without restriction, including without limitation the rights
  62 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  63 copies of the Software, and to permit persons to whom the Software is
  64 furnished to do so, subject to the following conditions:
  65
  66 The above copyright notice and this permission notice shall be included in
  67 all copies or substantial portions of the Software.
  68
  69 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  70 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  71 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  72 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  73 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  74 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  75
  76 Except as contained in this notice, the name of the X Consortium shall not be
  77 used in advertising or otherwise to promote the sale, use or other dealings
  78 in this Software without prior written authorization from the X Consortium.
  79
  80
  81 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
  82
  83                         All Rights Reserved
  84
  85 Permission to use, copy, modify, and distribute this software and its
  86 documentation for any purpose and without fee is hereby granted,
  87 provided that the above copyright notice appear in all copies and that
  88 both that copyright notice and this permission notice appear in
  89 supporting documentation, and that the name of Digital not be
  90 used in advertising or publicity pertaining to distribution of the
  91 software without specific, written prior permission.
  92
  93 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  94 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  95 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  96 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  97 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  98 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  99 SOFTWARE.
 100 ******************************************************************/
 101
 102 /*
 103  *     Written by Brian Kelleher; Dec. 1985.
 104  *     Adapted for Microwindows Sep 2001 by Greg Haerr <greg@censoft.com>
 105  *
 106  *     Fill a convex polygon in the fg color, with clipping.
 107  *     If the given polygon
 108  *     is not convex, then the result is undefined.
 109  *     The algorithm is to order the edges from smallest
 110  *     y to largest by partitioning the array into a left
 111  *     edge list and a right edge list.  The algorithm used
 112  *     to traverse each edge is an extension of Bresenham's
 113  *     line algorithm with y as the major axis.
 114  *
 115  *     This file contains a few macros to help track
 116  *     the edge of a filled object.  The object is assumed
 117  *     to be filled in scanline order, and thus the
 118  *     algorithm used is an extension of Bresenham's line
 119  *     drawing algorithm which assumes that y is always the
 120  *     major axis.
 121  *
 122  *  In scan converting polygons, we want to choose those pixels
 123  *  which are inside the polygon.  Thus, we add .5 to the starting
 124  *  x coordinate for both left and right edges.  Now we choose the
 125  *  first pixel which is inside the pgon for the left edge and the
 126  *  first pixel which is outside the pgon for the right edge.
 127  *  Draw the left pixel, but not the right.
 128  *
 129  *  How to add .5 to the starting x coordinate:
 130  *      If the edge is moving to the right, then subtract dy from the
 131  *  error term from the general form of the algorithm.
 132  *      If the edge is moving to the left, then add dy to the error term.
 133  *
 134  *  The reason for the difference between edges moving to the left
 135  *  and edges moving to the right is simple:  If an edge is moving
 136  *  to the right, then we want the algorithm to flip immediately.
 137  *  If it is moving to the left, then we don't want it to flip until
 138  *  we traverse an entire pixel.
 139  */
 140 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
 141     int dx;      /* local storage */ \
 142 \
 143     /* \
 144      *  if the edge is horizontal, then it is ignored \
 145      *  and assumed not to be processed.  Otherwise, do this stuff. \
 146      */ \
 147     if ((dy) != 0) { \
 148         xStart = (x1); \
 149         dx = (x2) - xStart; \
 150         if (dx < 0) { \
 151             m = dx / (dy); \
 152             m1 = m - 1; \
 153             incr1 = -2 * dx + 2 * (dy) * m1; \
 154             incr2 = -2 * dx + 2 * (dy) * m; \
 155             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
 156         } else { \
 157             m = dx / (dy); \
 158             m1 = m + 1; \
 159             incr1 = 2 * dx - 2 * (dy) * m1; \
 160             incr2 = 2 * dx - 2 * (dy) * m; \
 161             d = -2 * m * (dy) + 2 * dx; \
 162         } \
 163     } \
 164 }
 165
 166 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
 167     if (m1 > 0) { \
 168         if (d > 0) { \
 169             minval += m1; \
 170             d += incr1; \
 171         } \
 172         else { \
 173             minval += m; \
 174             d += incr2; \
 175         } \
 176     } else {\
 177         if (d >= 0) { \
 178             minval += m1; \
 179             d += incr1; \
 180         } \
 181         else { \
 182             minval += m; \
 183             d += incr2; \
 184         } \
 185     } \
 186 }
 187
 188 /*
 189  *     Find the index of the point with the smallest y.
 190  */
 191 static int
 192 getPolyYBounds(MWPOINT *pts, int n, int *by, int *ty)
 193 {
 194     MWPOINT *ptMin;
 195     int ymin, ymax;
 196     MWPOINT *ptsStart = pts;
 197
 198     ptMin = pts;
 199     ymin = ymax = (pts++)->y;
 200
 201     while (--n > 0) {
 202         if (pts->y < ymin)
 203         {
 204             ptMin = pts;
 205             ymin = pts->y;
 206         }
 207         if(pts->y > ymax)
 208             ymax = pts->y;
 209
 210         pts++;
 211     }
 212
 213     *by = ymin;
 214     *ty = ymax;
 215     return(ptMin-ptsStart);
 216 }
 217
 218 void
 219 GdFillPoly(PSD psd, int count, MWPOINT *pointtable)
 220 {
 221     MWCOORD xl = 0, xr = 0;     /* x vals of left and right edges */
 222     int dl = 0, dr = 0;         /* decision variables             */
 223     int ml = 0, m1l = 0;        /* left edge slope and slope+1    */
 224     int mr = 0, m1r = 0;        /* right edge slope and slope+1   */
 225     int incr1l = 0, incr2l = 0; /* left edge error increments     */
 226     int incr1r = 0, incr2r = 0; /* right edge error increments    */
 227     int dy;                     /* delta y                        */
 228     MWCOORD y;                  /* current scanline               */
 229     int left, right;            /* indices to first endpoints     */
 230     int i;                      /* loop counter                   */
 231     int nextleft, nextright;    /* indices to second endpoints    */
 232     MWPOINT *ptsOut, *FirstPoint;/* output buffer                 */
 233     MWCOORD *width, *FirstWidth;/* output buffer                  */
 234     int imin;                   /* index of smallest vertex (in y)*/
 235     int ymin;                   /* y-extents of polygon           */
 236     int ymax;
 237
 238     /*
 239      *  find leftx, bottomy, rightx, topy, and the index
 240      *  of bottomy.
 241      */
 242     imin = getPolyYBounds(pointtable, count, &ymin, &ymax);
 243
 244     dy = ymax - ymin + 1;
 245     if ((count < 3) || (dy < 0))
 246         return;
 247     ptsOut = FirstPoint = (MWPOINT *)ALLOCA(sizeof(MWPOINT) * dy);
 248     width = FirstWidth = (MWCOORD *)ALLOCA(sizeof(MWCOORD) * dy);
 249     if(!FirstPoint || !FirstWidth)
 250     {
 251         if (FirstWidth) FREEA(FirstWidth);
 252         if (FirstPoint) FREEA(FirstPoint);
 253         return;
 254     }
 255
 256     nextleft = nextright = imin;
 257     y = pointtable[nextleft].y;
 258
 259     /*
 260      *  loop through all edges of the polygon
 261      */
 262     do {
 263         /*
 264          *  add a left edge if we need to
 265          */
 266         if (pointtable[nextleft].y == y) {
 267             left = nextleft;
 268
 269             /*
 270              *  find the next edge, considering the end
 271              *  conditions of the array.
 272              */
 273             nextleft++;
 274             if (nextleft >= count)
 275                 nextleft = 0;
 276
 277             /*
 278              *  now compute all of the random information
 279              *  needed to run the iterative algorithm.
 280              */
 281             BRESINITPGON(pointtable[nextleft].y-pointtable[left].y,
 282                          pointtable[left].x,pointtable[nextleft].x,
 283                          xl, dl, ml, m1l, incr1l, incr2l);
 284         }
 285
 286         /*
 287          *  add a right edge if we need to
 288          */
 289         if (pointtable[nextright].y == y) {
 290             right = nextright;
 291
 292             /*
 293              *  find the next edge, considering the end
 294              *  conditions of the array.
 295              */
 296             nextright--;
 297             if (nextright < 0)
 298                 nextright = count-1;
 299
 300             /*
 301              *  now compute all of the random information
 302              *  needed to run the iterative algorithm.
 303              */
 304             BRESINITPGON(pointtable[nextright].y-pointtable[right].y,
 305                          pointtable[right].x,pointtable[nextright].x,
 306                          xr, dr, mr, m1r, incr1r, incr2r);
 307         }
 308
 309         /*
 310          *  generate scans to fill while we still have
 311          *  a right edge as well as a left edge.
 312          */
 313         i = MWMIN(pointtable[nextleft].y, pointtable[nextright].y) - y;
 314         /* in case we're called with non-convex polygon */
 315         if(i < 0)
 316         {
 317             FREEA(FirstWidth);
 318             FREEA(FirstPoint);
 319             return;
 320         }
 321         while (i-- > 0)
 322         {
 323             ptsOut->y = y;
 324
 325             /*
 326              *  reverse the edges if necessary
 327              */
 328             if (xl < xr)
 329             {
 330                 *(width++) = xr - xl;
 331                 (ptsOut++)->x = xl;
 332             }
 333             else
 334             {
 335                 *(width++) = xl - xr;
 336                 (ptsOut++)->x = xr;
 337             }
 338             y++;
 339
 340             /* increment down the edges */
 341             BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
 342             BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
 343         }
 344     }  while (y != ymax);
 345
 346     /*
 347      * Finally, fill the spans
 348      */
 349     i = ptsOut-FirstPoint;
 350     ptsOut = FirstPoint;
 351     width = FirstWidth;
 352     while (--i >= 0) {
 353         /* calc x extent from width*/
 354         int e = *width++ - 1;
 355         if (e >= 0) {
 356             drawrow(psd, ptsOut->x, ptsOut->x + e, ptsOut->y);
 357         }
 358         ++ptsOut;
 359     }
 360
 361     FREEA(FirstWidth);
 362     FREEA(FirstPoint);
 363     GdFixCursor(psd);
 364 }
 365 #endif
 366
 367 #if 0 /* original convex only polygon fill routine*/
 368 /*
 369  * Fill a polygon in the foreground color, applying clipping if necessary.
 370  * The last point may be a duplicate of the first point, but this is
 371  * not required.
 372  * Note: this routine currently only correctly fills convex polygons.
 373  */
 374
 375 /* Utility routine for filling polygons.  Find the intersection point (if
 376  * any) of a horizontal line with an arbitrary line, and extend the current
 377  * minimum and maximum x values as needed to include the intersection point.
 378  * Input parms:
 379  *      y       row to check for intersection
 380  *      x1, y1  first endpoint
 381  *      x2, y2  second enpoint
 382  *      minxptr address of current minimum x
 383  *      maxxptr address of current maximum x
 384  */
 385 static void
 386 extendrow(MWCOORD y,MWCOORD x1,MWCOORD y1,MWCOORD x2,MWCOORD y2,
 387         MWCOORD *minxptr,MWCOORD *maxxptr)
 388 {
 389   MWCOORD x;                    /* x coordinate of intersection */
 390   typedef long NUM;
 391   NUM num;                      /* numerator of fraction */
 392
 393   /* First make sure the specified line segment includes the specified
 394    * row number.  If not, then there is no intersection.
 395    */
 396   if (((y < y1) || (y > y2)) && ((y < y2) || (y > y1)))
 397         return;
 398
 399   /* If a horizontal line, then check the two endpoints. */
 400   if (y1 == y2) {
 401         if (*minxptr > x1) *minxptr = x1;
 402         if (*minxptr > x2) *minxptr = x2;
 403         if (*maxxptr < x1) *maxxptr = x1;
 404         if (*maxxptr < x2) *maxxptr = x2;
 405         return;
 406   }
 407
 408   /* If a vertical line, then check the x coordinate. */
 409   if (x1 == x2) {
 410         if (*minxptr > x1) *minxptr = x1;
 411         if (*maxxptr < x1) *maxxptr = x1;
 412         return;
 413   }
 414
 415   /* An arbitrary line.  Calculate the intersection point using the
 416    * formula x = x1 + (y - y1) * (x2 - x1) / (y2 - y1).
 417    */
 418   num = ((NUM) (y - y1)) * (x2 - x1);
 419   x = x1 + num / (y2 - y1);
 420   if (*minxptr > x) *minxptr = x;
 421   if (*maxxptr < x) *maxxptr = x;
 422 }
 423
 424 void
 425 GdFillPoly(PSD psd, int count, MWPOINT *points)
 426 {
 427   MWPOINT *pp;          /* current point */
 428   MWCOORD miny;         /* minimum row */
 429   MWCOORD maxy;         /* maximum row */
 430   MWCOORD minx;         /* minimum column */
 431   MWCOORD maxx;         /* maximum column */
 432   int i;                /* counter */
 433
 434   if (count <= 0)
 435           return;
 436
 437   /* First determine the minimum and maximum rows for the polygon. */
 438   pp = points;
 439   miny = pp->y;
 440   maxy = pp->y;
 441   for (i = count; i-- > 0; pp++) {
 442         if (miny > pp->y) miny = pp->y;
 443         if (maxy < pp->y) maxy = pp->y;
 444   }
 445   if (miny < 0)
 446           miny = 0;
 447   if (maxy >= psd->yvirtres)
 448           maxy = psd->yvirtres - 1;
 449   if (miny > maxy)
 450           return;
 451
 452   /* Now for each row, scan the list of points and determine the
 453    * minimum and maximum x coordinate for each line, and plot the row.
 454    * The last point connects with the first point automatically.
 455    */
 456   for (; miny <= maxy; miny++) {
 457         minx = MAX_MWCOORD;
 458         maxx = MIN_MWCOORD;
 459         pp = points;
 460         for (i = count; --i > 0; pp++)
 461                 extendrow(miny, pp[0].x, pp[0].y, pp[1].x, pp[1].y,
 462                         &minx, &maxx);
 463         extendrow(miny, pp[0].x, pp[0].y, points[0].x, points[0].y,
 464                 &minx, &maxx);
 465
 466         if (minx <= maxx)
 467                 drawrow(psd, minx, maxx, miny);
 468   }
 469   GdFixCursor(psd);
 470 }
 471 #endif
 472
 473 #if 0   /* irregular polygon fill, uses edge table, malloc, qsort*/
 474 /*
 475  * Fill a polygon in the foreground color, applying clipping if necessary.
 476  * The last point may be a duplicate of the first point, but this is
 477  * not required.
 478  * Note: this routine correctly draws convex, concave, regular,
 479  * and irregular polygons.
 480  */
 481 #define USE_FLOAT       HAVEFLOAT       /* set to use floating point*/
 482
 483 #define swap(a,b) do { a ^= b; b ^= a; a ^= b; } while (0)
 484
 485 typedef struct {
 486         int     x1, y1, x2, y2;
 487 #if USE_FLOAT
 488         double  x, m;
 489 #else
 490         int     cx, fn, mn, d;
 491 #endif
 492 } edge_t;
 493
 494 static int
 495 edge_cmp(const void *lvp, const void *rvp)
 496 {
 497         /* convert from void pointers to structure pointers */
 498         const edge_t *lp = (const edge_t *)lvp;
 499         const edge_t *rp = (const edge_t *)rvp;
 500
 501         /* if the minimum y values are different, sort on minimum y */
 502         if (lp->y1 != rp->y1)
 503                 return lp->y1 - rp->y1;
 504
 505         /* if the current x values are different, sort on current x */
 506 #if USE_FLOAT
 507         if (lp->x < rp->x)
 508                 return -1;
 509         else if (lp->x > rp->x)
 510                 return +1;
 511 #else
 512         if (lp->cx != rp->cx)
 513                 return lp->cx - rp->cx;
 514 #endif
 515
 516         /* otherwise they are equal */
 517         return 0;
 518 }
 519
 520 void
 521 GdFillPoly(PSD psd, int count, MWPOINT * pointtable)
 522 {
 523         edge_t *get;            /* global edge table */
 524         int     nge = 0;        /* num global edges */
 525         int     cge = 0;        /* cur global edge */
 526
 527         edge_t *aet;            /* active edge table */
 528         int     nae = 0;        /* num active edges */
 529
 530         int     i, y;
 531
 532         if (count < 3) {
 533                 /* error, polygons require at least three edges (a triangle) */
 534                 return;
 535         }
 536         get = (edge_t *) calloc(count, sizeof(edge_t));
 537         aet = (edge_t *) calloc(count, sizeof(edge_t));
 538
 539         if ((get == 0) || (aet == 0)) {
 540                 /* error, couldn't allocate one or both of the needed tables */
 541                 if (get)
 542                         free(get);
 543                 if (aet)
 544                         free(aet);
 545                 return;
 546         }
 547         /* setup the global edge table */
 548         for (i = 0; i < count; ++i) {
 549                 get[nge].x1 = pointtable[i].x;
 550                 get[nge].y1 = pointtable[i].y;
 551                 get[nge].x2 = pointtable[(i + 1) % count].x;
 552                 get[nge].y2 = pointtable[(i + 1) % count].y;
 553                 if (get[nge].y1 != get[nge].y2) {
 554                         if (get[nge].y1 > get[nge].y2) {
 555                                 swap(get[nge].x1, get[nge].x2);
 556                                 swap(get[nge].y1, get[nge].y2);
 557                         }
 558 #if USE_FLOAT
 559                         get[nge].x = get[nge].x1;
 560                         get[nge].m = get[nge].x2 - get[nge].x1;
 561                         get[nge].m /= get[nge].y2 - get[nge].y1;
 562 #else
 563                         get[nge].cx = get[nge].x1;
 564                         get[nge].mn = get[nge].x2 - get[nge].x1;
 565                         get[nge].d = get[nge].y2 - get[nge].y1;
 566                         get[nge].fn = get[nge].mn / 2;
 567 #endif
 568                         ++nge;
 569                 }
 570         }
 571
 572         qsort(get, nge, sizeof(get[0]), edge_cmp);
 573
 574         /* start with the lowest y in the table */
 575         y = get[0].y1;
 576
 577         do {
 578
 579                 /* add edges to the active table from the global table */
 580                 while ((nge > 0) && (get[cge].y1 == y)) {
 581                         aet[nae] = get[cge++];
 582                         --nge;
 583                         aet[nae++].y1 = 0;
 584                 }
 585
 586                 qsort(aet, nae, sizeof(aet[0]), edge_cmp);
 587
 588                 /* using odd parity, render alternating line segments */
 589                 for (i = 1; i < nae; i += 2) {
 590 #if USE_FLOAT
 591                         int     l = (int)aet[i - 1].x;
 592                         int     r = (int)aet[i].x;
 593 #else
 594                         int     l = (int)aet[i - 1].cx;
 595                         int     r = (int)aet[i].cx;
 596 #endif
 597                         if (r > l)
 598                                 drawrow(psd, l, r - 1, y);
 599                 }
 600
 601                 /* prepare for the next scan line */
 602                 ++y;
 603
 604                 /* remove inactive edges from the active edge table */
 605                 /* or update the current x position of active edges */
 606                 for (i = 0; i < nae; ++i) {
 607                         if (aet[i].y2 == y)
 608                                 aet[i--] = aet[--nae];
 609                         else {
 610 #if USE_FLOAT
 611                                 aet[i].x += aet[i].m;
 612 #else
 613                                 aet[i].fn += aet[i].mn;
 614                                 if (aet[i].fn < 0) {
 615                                         aet[i].cx += aet[i].fn / aet[i].d - 1;
 616                                         aet[i].fn %= aet[i].d;
 617                                         aet[i].fn += aet[i].d;
 618                                 }
 619                                 if (aet[i].fn >= aet[i].d) {
 620                                         aet[i].cx += aet[i].fn / aet[i].d;
 621                                         aet[i].fn %= aet[i].d;
 622                                 }
 623 #endif
 624                         }
 625                 }
 626
 627                 /* keep doing this while there are any edges left */
 628         } while ((nae > 0) || (nge > 0));
 629
 630         /* all done, free the edge tables */
 631         free(get);
 632         free(aet);
 633
 634         GdFixCursor(psd);
 635 }
 636 #endif