Return to mipolycon.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi

Annotation of researchv9/X11/src/X.V11R1/server/ddx/mi/mipolycon.c, revision 1.1

1.1     ! root        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: /* $Header: mipolycon.c,v 1.15 87/09/11 07:18:54 toddb Exp $ */
        !            25: #include "gcstruct.h"
        !            26: #include "pixmap.h"
        !            27: #include "miscanfill.h"
        !            28: 
        !            29: /*
        !            30:  *     convexpoly.c
        !            31:  *
        !            32:  *     Written by Brian Kelleher; Dec. 1985.
        !            33:  *
        !            34:  *     Fill a convex polygon.  If the given polygon
        !            35:  *     is not convex, then the result is undefined.
        !            36:  *     The algorithm is to order the edges from smallest
        !            37:  *     y to largest by partitioning the array into a left
        !            38:  *     edge list and a right edge list.  The algorithm used
        !            39:  *     to traverse each edge is an extension of Bresenham's
        !            40:  *     line algorithm with y as the major axis.
        !            41:  *     For a derivation of the algorithm, see the author of
        !            42:  *     this code.
        !            43:  */
        !            44: void
        !            45: miFillConvexPoly(dst, pgc, count, ptsIn)
        !            46:     DrawablePtr dst;
        !            47:     GCPtr      pgc;
        !            48:     int                count;                /* number of points        */
        !            49:     DDXPointPtr ptsIn;                /* the points              */
        !            50: {
        !            51:     register int xl, xr;        /* x vals of left and right edges */
        !            52:     register int dl, dr;        /* decision variables             */
        !            53:     register int ml, m1l;       /* left edge slope and slope+1    */
        !            54:     int mr, m1r;                /* right edge slope and slope+1   */
        !            55:     int incr1l, incr2l;         /* left edge error increments     */
        !            56:     int incr1r, incr2r;         /* right edge error increments    */
        !            57:     int dy;                     /* delta y                        */
        !            58:     int y;                      /* current scanline               */
        !            59:     int left, right;            /* indices to first endpoints     */
        !            60:     int i;                      /* loop counter                   */
        !            61:     int nextleft, nextright;    /* indices to second endpoints    */
        !            62:     DDXPointPtr ptsOut, FirstPoint; /* output buffer               */
        !            63:     int *width, *FirstWidth;    /* output buffer                  */
        !            64:     int imin;                   /* index of smallest vertex (in y) */
        !            65:     int ymin;                   /* y-extents of polygon            */
        !            66:     int ymax;
        !            67: 
        !            68:     /*
        !            69:      *  find leftx, bottomy, rightx, topy, and the index
        !            70:      *  of bottomy. Also translate the points.
        !            71:      */
        !            72:     imin = getPolyYBounds(ptsIn, count, &ymin, &ymax);
        !            73: 
        !            74:     dy = ymax - ymin + 1;
        !            75:     ptsOut = FirstPoint = (DDXPointPtr )ALLOCATE_LOCAL(sizeof(DDXPointRec)*dy);
        !            76:     width = FirstWidth = (int *)ALLOCATE_LOCAL(sizeof(int) * dy);
        !            77:     if(!ptsOut || !width)
        !            78:     {
        !            79:        DEALLOCATE_LOCAL(width);
        !            80:        DEALLOCATE_LOCAL(ptsOut);
        !            81:        return;
        !            82:     }
        !            83: 
        !            84:     if ((count < 3) || (dy < 0))
        !            85:     {
        !            86:        DEALLOCATE_LOCAL(width);
        !            87:        DEALLOCATE_LOCAL(ptsOut);
        !            88:        return;
        !            89:     }
        !            90: 
        !            91:     nextleft = nextright = imin;
        !            92:     y = ptsIn[nextleft].y;
        !            93: 
        !            94:     /*
        !            95:      *  loop through all edges of the polygon
        !            96:      */
        !            97:     do {
        !            98:         /*
        !            99:          *  add a left edge if we need to
        !           100:          */
        !           101:         if (ptsIn[nextleft].y == y) {
        !           102:             left = nextleft;
        !           103: 
        !           104:             /*
        !           105:              *  find the next edge, considering the end
        !           106:              *  conditions of the array.
        !           107:              */
        !           108:             nextleft++;
        !           109:             if (nextleft >= count)
        !           110:                 nextleft = 0;
        !           111: 
        !           112:             /*
        !           113:              *  now compute all of the random information
        !           114:              *  needed to run the iterative algorithm.
        !           115:              */
        !           116:             BRESINITPGON(ptsIn[nextleft].y-ptsIn[left].y,
        !           117:                          ptsIn[left].x,ptsIn[nextleft].x,
        !           118:                          xl, dl, ml, m1l, incr1l, incr2l);
        !           119:         }
        !           120: 
        !           121:         /*
        !           122:          *  add a right edge if we need to
        !           123:          */
        !           124:         if (ptsIn[nextright].y == y) {
        !           125:             right = nextright;
        !           126: 
        !           127:             /*
        !           128:              *  find the next edge, considering the end
        !           129:              *  conditions of the array.
        !           130:              */
        !           131:             nextright--;
        !           132:             if (nextright < 0)
        !           133:                 nextright = count-1;
        !           134: 
        !           135:             /*
        !           136:              *  now compute all of the random information
        !           137:              *  needed to run the iterative algorithm.
        !           138:              */
        !           139:             BRESINITPGON(ptsIn[nextright].y-ptsIn[right].y,
        !           140:                          ptsIn[right].x,ptsIn[nextright].x,
        !           141:                          xr, dr, mr, m1r, incr1r, incr2r);
        !           142:         }
        !           143: 
        !           144:         /*
        !           145:          *  generate scans to fill while we still have
        !           146:          *  a right edge as well as a left edge.
        !           147:          */
        !           148:         i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
        !           149:        /* in case we're called with non-convex polygon */
        !           150:        if(i < 0)
        !           151:         {
        !           152:            DEALLOCATE_LOCAL(FirstWidth);
        !           153:            DEALLOCATE_LOCAL(FirstPoint);
        !           154:            return;
        !           155:        }
        !           156:         while (i-- > 0) 
        !           157:         {
        !           158:             ptsOut->y = y;
        !           159: 
        !           160:             /*
        !           161:              *  reverse the edges if necessary
        !           162:              */
        !           163:             if (xl < xr) 
        !           164:             {
        !           165:                 *(width++) = xr - xl;
        !           166:                 (ptsOut++)->x = xl;
        !           167:             }
        !           168:             else 
        !           169:             {
        !           170:                 *(width++) = xl - xr;
        !           171:                 (ptsOut++)->x = xr;
        !           172:             }
        !           173:             y++;
        !           174: 
        !           175:             /* increment down the edges */
        !           176:             BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
        !           177:             BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
        !           178:         }
        !           179:     }  while (y != ymax);
        !           180: 
        !           181:     /*
        !           182:      * Finally, fill the <remaining> spans
        !           183:      */
        !           184:     (*pgc->FillSpans)(dst, pgc, 
        !           185:                      ptsOut-FirstPoint,FirstPoint,FirstWidth,
        !           186:                      1);
        !           187:     DEALLOCATE_LOCAL(FirstWidth);
        !           188:     DEALLOCATE_LOCAL(FirstPoint);
        !           189: }
        !           190: 
        !           191: 
        !           192: /*
        !           193:  *     Find the index of the point with the smallest y.
        !           194:  */
        !           195: static
        !           196: int
        !           197: getPolyYBounds(pts, n, by, ty)
        !           198:     DDXPointPtr pts;
        !           199:     int n;
        !           200:     int *by, *ty;
        !           201: {
        !           202:     register DDXPointPtr ptMin;
        !           203:     int ymin, ymax;
        !           204:     DDXPointPtr ptsStart = pts;
        !           205: 
        !           206:     ptMin = pts;
        !           207:     ymin = ymax = (pts++)->y;
        !           208: 
        !           209:     while (--n > 0) {
        !           210:         if (pts->y < ymin)
        !           211:        {
        !           212:             ptMin = pts;
        !           213:             ymin = pts->y;
        !           214:         }
        !           215:        if(pts->y > ymax)
        !           216:             ymax = pts->y;
        !           217: 
        !           218:         pts++;
        !           219:     }
        !           220: 
        !           221:     *by = ymin;
        !           222:     *ty = ymax;
        !           223:     return(ptMin-ptsStart);
        !           224: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.