home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / server / ddx / mi / mifpolycon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-07-28  |  7.2 KB  |  255 lines
  1. /***********************************************************
  2. Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
  3. and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its 
  8. documentation for any purpose and without fee is hereby granted, 
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in 
  11. supporting documentation, and that the names of Digital or MIT not be
  12. used in advertising or publicity pertaining to distribution of the
  13. software without specific, written prior permission.  
  14.  
  15. DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  16. ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  17. DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  18. ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  19. WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  20. ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  21. SOFTWARE.
  22.  
  23. ******************************************************************/
  24. /* $XConsortium: mifpolycon.c,v 5.3 89/07/28 12:13:45 rws Exp $ */
  25. #include <math.h>
  26. #include "X.h"
  27. #include "gcstruct.h"
  28. #include "windowstr.h"
  29. #include "pixmapstr.h"
  30. #include "mifpoly.h"
  31.  
  32. static int GetFPolyYBounds();
  33.  
  34. #ifdef ICEILTEMPDECL
  35. ICEILTEMPDECL
  36. #endif
  37.  
  38. /*
  39.  *    Written by Todd Newman; April. 1987.
  40.  *
  41.  *    Fill a convex polygon.  If the given polygon
  42.  *    is not convex, then the result is undefined.
  43.  *    The algorithm is to order the edges from smallest
  44.  *    y to largest by partitioning the array into a left
  45.  *    edge list and a right edge list.  The algorithm used
  46.  *    to traverse each edge is digital differencing analyzer
  47.  *    line algorithm with y as the major axis. There's some funny linear
  48.  *    interpolation involved because of the subpixel postioning.
  49.  */
  50. void
  51. miFillSppPoly(dst, pgc, count, ptsIn, xTrans, yTrans, xFtrans, yFtrans)
  52.     DrawablePtr     dst;
  53.     GCPtr        pgc;
  54.     int            count;          /* number of points */
  55.     SppPointPtr     ptsIn;          /* the points */
  56.     int            xTrans, yTrans;    /* Translate each point by this */
  57.     double        xFtrans, yFtrans;    /* translate before conversion
  58.                                by this amount.  This provides
  59.                            a mechanism to match rounding
  60.                            errors with any shape that must
  61.                            meet the polygon exactly.
  62.                          */
  63. {
  64.     double        xl, xr,        /* x vals of left and right edges */
  65.                   ml,           /* left edge slope */
  66.                   mr,             /* right edge slope */
  67.                   dy,             /* delta y */
  68.                 i;              /* loop counter */
  69.     int            y,              /* current scanline */
  70.                 j,
  71.                 imin,           /* index of vertex with smallest y */
  72.                 ymin,           /* y-extents of polygon */
  73.                 ymax,
  74.                 *width,
  75.                 *FirstWidth,    /* output buffer */
  76.                  *Marked;    /* set if this vertex has been used */
  77.     register int    left, right,    /* indices to first endpoints */
  78.                 nextleft,
  79.                      nextright;    /* indices to second endpoints */
  80.     DDXPointPtr     ptsOut,
  81.                 FirstPoint;    /* output buffer */
  82.  
  83.     if (pgc->miTranslate)
  84.     {
  85.     xTrans += dst->x;
  86.     yTrans += dst->y;
  87.     }
  88.  
  89.     imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax);
  90.  
  91.     y = ymax - ymin + 1;
  92.     if ((count < 3) || (y <= 0))
  93.     return;
  94.     ptsOut = FirstPoint = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * y);
  95.     width = FirstWidth = (int *) ALLOCATE_LOCAL(sizeof(int) * y);
  96.     Marked = (int *) ALLOCATE_LOCAL(sizeof(int) * count);
  97.  
  98.     if(!ptsOut || !width || !Marked)
  99.     {
  100.     if (Marked) DEALLOCATE_LOCAL(Marked);
  101.     if (width) DEALLOCATE_LOCAL(width);
  102.     if (ptsOut) DEALLOCATE_LOCAL(ptsOut);
  103.     return;
  104.     }
  105.  
  106.     for(j = 0; j < count; j++)
  107.     Marked[j] = 0;
  108.     nextleft = nextright = imin;
  109.     Marked[imin] = -1;
  110.     y = ICEIL(ptsIn[nextleft].y + yFtrans);
  111.  
  112.     /*
  113.      *  loop through all edges of the polygon
  114.      */
  115.     do
  116.     {
  117.         /* add a left edge if we need to */
  118.         if ((y > (ptsIn[nextleft].y + yFtrans) ||
  119.           ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) &&
  120.          Marked[nextleft] != 1)
  121.     {
  122.         Marked[nextleft]++;
  123.             left = nextleft++;
  124.  
  125.             /* find the next edge, considering the end conditions */
  126.             if (nextleft >= count)
  127.                 nextleft = 0;
  128.  
  129.             /* now compute the starting point and slope */
  130.         dy = ptsIn[nextleft].y - ptsIn[left].y;
  131.         if (dy != 0.0)
  132.         { 
  133.         ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy;
  134.         dy = y - (ptsIn[left].y + yFtrans);
  135.         xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0); 
  136.         }
  137.         }
  138.  
  139.         /* add a right edge if we need to */
  140.         if ((y > ptsIn[nextright].y + yFtrans) ||
  141.           ISEQUAL(y, ptsIn[nextright].y + yFtrans)
  142.          && Marked[nextright] != 1)
  143.     {
  144.         Marked[nextright]++;
  145.             right = nextright--;
  146.  
  147.             /* find the next edge, considering the end conditions */
  148.             if (nextright < 0)
  149.                 nextright = count - 1;
  150.  
  151.             /* now compute the starting point and slope */
  152.         dy = ptsIn[nextright].y - ptsIn[right].y;
  153.         if (dy != 0.0) 
  154.         { 
  155.         mr = (ptsIn[nextright].x - ptsIn[right].x) / dy;
  156.         dy = y - (ptsIn[right].y + yFtrans); 
  157.         xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0);
  158.         }
  159.         }
  160.  
  161.  
  162.         /*
  163.          *  generate scans to fill while we still have
  164.          *  a right edge as well as a left edge.
  165.          */
  166.         i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y;
  167.  
  168.     if (i < EPSILON)
  169.     {
  170.         if(Marked[nextleft] && Marked[nextright])
  171.         {
  172.             /* Arrgh, we're trapped! (no more points) 
  173.              * Out, we've got to get out of here before this decadence saps
  174.              * our will completely! */
  175.             break;
  176.         }
  177.         continue;
  178.     }
  179.     else
  180.     {
  181.         j = (int) i;
  182.         if(!j)
  183.             j++;
  184.     }
  185.         while (j > 0) 
  186.         {
  187.         int cxl, cxr;
  188.  
  189.             ptsOut->y = (y) + yTrans;
  190.  
  191.         cxl = ICEIL(xl);
  192.         cxr = ICEIL(xr);
  193.             /* reverse the edges if necessary */
  194.             if (xl < xr) 
  195.             {
  196.                 *(width++) = cxr - cxl;
  197.                 (ptsOut++)->x = cxl + xTrans;
  198.             }
  199.             else 
  200.             {
  201.                 *(width++) = cxl - cxr;
  202.                 (ptsOut++)->x = cxr + xTrans;
  203.             }
  204.             y++;
  205.  
  206.             /* increment down the edges */
  207.         xl += ml;
  208.         xr += mr;
  209.         j--;
  210.         }
  211.     }  while (y <= ymax);
  212.  
  213.     /* Finally, fill the spans we've collected */
  214.     (*pgc->ops->FillSpans)(dst, pgc, 
  215.               ptsOut-FirstPoint, FirstPoint, FirstWidth, 1);
  216.     DEALLOCATE_LOCAL(Marked);
  217.     DEALLOCATE_LOCAL(FirstWidth);
  218.     DEALLOCATE_LOCAL(FirstPoint);
  219. }
  220.  
  221.  
  222. /* Find the index of the point with the smallest y.also return the
  223.  * smallest and largest y */
  224. static
  225. int
  226. GetFPolyYBounds(pts, n, yFtrans, by, ty)
  227.     register SppPointPtr    pts;
  228.     int             n;
  229.     double            yFtrans;
  230.     int             *by, *ty;
  231. {
  232.     register SppPointPtr    ptMin;
  233.     double             ymin, ymax;
  234.     SppPointPtr            ptsStart = pts;
  235.  
  236.     ptMin = pts;
  237.     ymin = ymax = (pts++)->y;
  238.  
  239.     while (--n > 0) {
  240.         if (pts->y < ymin)
  241.     {
  242.             ptMin = pts;
  243.             ymin = pts->y;
  244.         }
  245.     if(pts->y > ymax)
  246.             ymax = pts->y;
  247.  
  248.         pts++;
  249.     }
  250.  
  251.     *by = ICEIL(ymin + yFtrans);
  252.     *ty = ICEIL(ymax + yFtrans - 1);
  253.     return(ptMin-ptsStart);
  254. }
  255.