Return to mifpolycon.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/mifpolycon.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: mifpolycon.c,v 1.10 87/09/11 07:20:50 toddb Exp $ */
        !            25: #include "X.h"
        !            26: #include "gcstruct.h"
        !            27: #include "windowstr.h"
        !            28: #include "pixmapstr.h"
        !            29: #include "mifpoly.h"
        !            30: 
        !            31: /*
        !            32:  *     Written by Todd Newman; April. 1987.
        !            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 digital differencing analyzer
        !            40:  *     line algorithm with y as the major axis. There's some funny linear
        !            41:  *     interpolation involved because of the subpixel postioning.
        !            42:  *
        !            43:  *     Given the opportunity to write non-portable code, I would replace
        !            44:  *     this with a fixed point extended precision Bresenham line algorithm.
        !            45:  *     Instead of doubles in the SppPointRecs, I'd use 64 bit fixed point
        !            46:  *     values.  I'd have to write a fixed point math pack in assembler,
        !            47:  *     but these things are relatively straight forward. (Alas, not portable.)
        !            48:  *     
        !            49:  *     It can be shown that given 16 bit values for x and y, there's no
        !            50:  *     room to extend the precision and still fit intermediate results in
        !            51:  *     a 32 bit integer.  It should also be clear that trying to write a
        !            52:  *     extended precision math pack in C would not produce code that runs
        !            53:  *     much faster than your average floating point coprocessor.  Even
        !            54:  *     floating point emulation should be able to run faster if the assembly
        !            55:  *     language coding is handled at all well.
        !            56:  *
        !            57:  *     "So why not at least use float, instead of double," my friends ask
        !            58:  *     me.  Well, C is going to cast everything to double as soon as you
        !            59:  *     try to do anything with it anyway.  (Check out K&R.)  I'd rather
        !            60:  *     trade a little space and skip all the superflous type conversions.
        !            61:  *     (This decision could be revisited if you have an ANSI C compiler.)
        !            62:  *
        !            63:  *     So, in sum, I apologize for doing all the wide lines with doubles,
        !            64:  *     but it seems the best trade off  of complexity, performance, and
        !            65:  *     time pressure.
        !            66:  */
        !            67: void
        !            68: miFillSppPoly(dst, pgc, count, ptsIn, xTrans, yTrans)
        !            69:     DrawablePtr        dst;
        !            70:     GCPtr              pgc;
        !            71:     int                        count;          /* number of points */
        !            72:     SppPointPtr        ptsIn;          /* the points */
        !            73:     int                        xTrans, yTrans; /* Translate each point by this */
        !            74: {
        !            75:     double             xl, xr,         /* x vals of left and right edges */
        !            76:                        ml,             /* left edge slope */
        !            77:                        mr,             /* right edge slope */
        !            78:                        dy,             /* delta y */
        !            79:                        i;              /* loop counter */
        !            80:     int                        y,              /* current scanline */
        !            81:                        j,
        !            82:                        imin,           /* index of vertex with smallest y */
        !            83:                        ymin,           /* y-extents of polygon */
        !            84:                        ymax,
        !            85:                        *width,
        !            86:                        *FirstWidth,    /* output buffer */
        !            87:                        *Marked;        /* set if this vertex has been used */
        !            88:     register int       left, right,    /* indices to first endpoints */
        !            89:                        nextleft,
        !            90:                        nextright;      /* indices to second endpoints */
        !            91:     DDXPointPtr        ptsOut,
        !            92:                        FirstPoint;     /* output buffer */
        !            93:     double             ceil();
        !            94: 
        !            95:     if (pgc->miTranslate && (dst->type == DRAWABLE_WINDOW) )
        !            96:     {
        !            97:        xTrans += ((WindowPtr)dst)->absCorner.x;
        !            98:        yTrans += ((WindowPtr)dst)->absCorner.y;
        !            99:     }
        !           100: 
        !           101:     imin = GetFPolyYBounds(ptsIn, count, &ymin, &ymax);
        !           102: 
        !           103:     y = ymax - ymin + 1;
        !           104:     ptsOut = FirstPoint = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * y);
        !           105:     width = FirstWidth = (int *) ALLOCATE_LOCAL(sizeof(int) * y);
        !           106:     Marked = (int *) ALLOCATE_LOCAL(sizeof(int) * count);
        !           107: 
        !           108:     if(!ptsOut || !width || !Marked || (count < 3) || (y <= 0))
        !           109:     {
        !           110:        DEALLOCATE_LOCAL(Marked);
        !           111:        DEALLOCATE_LOCAL(width);
        !           112:        DEALLOCATE_LOCAL(ptsOut);
        !           113:        return;
        !           114:     }
        !           115: 
        !           116:     for(j = 0; j < count; j++)
        !           117:        Marked[j] = 0;
        !           118:     nextleft = nextright = imin;
        !           119:     Marked[imin] = -1;
        !           120:     y = (int) ceil(ptsIn[nextleft].y);
        !           121: 
        !           122:     /*
        !           123:      *  loop through all edges of the polygon
        !           124:      */
        !           125:     do
        !           126:     {
        !           127:         /* add a left edge if we need to */
        !           128:         if ((y > ptsIn[nextleft].y || ISEQUAL(y, ptsIn[nextleft].y)) &&
        !           129:             Marked[nextleft] != 1)
        !           130:        {
        !           131:            Marked[nextleft]++;
        !           132:             left = nextleft++;
        !           133: 
        !           134:             /* find the next edge, considering the end conditions */
        !           135:             if (nextleft >= count)
        !           136:                 nextleft = 0;
        !           137: 
        !           138:             /* now compute the starting point and slope */
        !           139:            dy = ptsIn[nextleft].y - ptsIn[left].y;
        !           140:            if (dy != 0.0)
        !           141:            { 
        !           142:                ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy;
        !           143:                dy = y - ptsIn[left].y;
        !           144:                xl = ptsIn[left].x  + ml * max(dy, 0); 
        !           145:            }
        !           146:         }
        !           147: 
        !           148:         /* add a right edge if we need to */
        !           149:         if (((y > ptsIn[nextright].y) || ISEQUAL(y, ptsIn[nextright].y))
        !           150:             && Marked[nextright] != 1)
        !           151:        {
        !           152:            Marked[nextright]++;
        !           153:             right = nextright--;
        !           154: 
        !           155:             /* find the next edge, considering the end conditions */
        !           156:             if (nextright < 0)
        !           157:                 nextright = count - 1;
        !           158: 
        !           159:             /* now compute the starting point and slope */
        !           160:            dy = ptsIn[nextright].y - ptsIn[right].y;
        !           161:            if (dy != 0.0) 
        !           162:            { 
        !           163:                mr = (ptsIn[nextright].x - ptsIn[right].x) / dy;
        !           164:                dy = y - ptsIn[right].y; 
        !           165:                xr = ptsIn[right].x + mr * max(dy, 0);
        !           166:            }
        !           167:         }
        !           168: 
        !           169: 
        !           170:         /*
        !           171:          *  generate scans to fill while we still have
        !           172:          *  a right edge as well as a left edge.
        !           173:          */
        !           174:         i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
        !           175: 
        !           176:        if (i < EPSILON)
        !           177:        {
        !           178:            if(Marked[nextleft] && Marked[nextright])
        !           179:            {
        !           180:                /* Arrgh, we're trapped! (no more points) 
        !           181:                 * Out, we've got to get out of here before this decadence saps
        !           182:                 * our will completely! */
        !           183:                break;
        !           184:            }
        !           185:            continue;
        !           186:        }
        !           187:        else
        !           188:        {
        !           189:                j = (int) i;
        !           190:                if(!j)
        !           191:                    j++;
        !           192:        }
        !           193:         while (j > 0) 
        !           194:         {
        !           195:             ptsOut->y = (y) + yTrans;
        !           196: 
        !           197:             /* reverse the edges if necessary */
        !           198:             if (xl < xr) 
        !           199:             {
        !           200:                 *(width++) = ROUNDTOINT(xr) - ROUNDTOINT(xl);
        !           201:                 (ptsOut++)->x = ROUNDTOINT(xl) + xTrans;
        !           202:             }
        !           203:             else 
        !           204:             {
        !           205:                 *(width++) = ROUNDTOINT(xl) - ROUNDTOINT(xr);
        !           206:                 (ptsOut++)->x = ROUNDTOINT(xr) + xTrans;
        !           207:             }
        !           208:             y++;
        !           209: 
        !           210:             /* increment down the edges */
        !           211:            xl += ml;
        !           212:            xr += mr;
        !           213:            j--;
        !           214:         }
        !           215:     }  while (y < ymax);
        !           216: 
        !           217:     /* Finally, fill the spans we've collected */
        !           218:     (*pgc->FillSpans)(dst, pgc, 
        !           219:                      ptsOut-FirstPoint, FirstPoint, FirstWidth, 1);
        !           220:     DEALLOCATE_LOCAL(Marked);
        !           221:     DEALLOCATE_LOCAL(FirstWidth);
        !           222:     DEALLOCATE_LOCAL(FirstPoint);
        !           223: }
        !           224: 
        !           225: 
        !           226: /* Find the index of the point with the smallest y.also return the
        !           227:  * smallest and largest y */
        !           228: static
        !           229: int
        !           230: GetFPolyYBounds(pts, n, by, ty)
        !           231:     register SppPointPtr       pts;
        !           232:     int                        n;
        !           233:     int                        *by, *ty;
        !           234: {
        !           235:     register SppPointPtr       ptMin;
        !           236:     double                     ymin, ymax, ceil();
        !           237:     SppPointPtr                        ptsStart = pts;
        !           238: 
        !           239:     ptMin = pts;
        !           240:     ymin = ymax = (pts++)->y;
        !           241: 
        !           242:     while (--n > 0) {
        !           243:         if (pts->y < ymin)
        !           244:        {
        !           245:             ptMin = pts;
        !           246:             ymin = pts->y;
        !           247:         }
        !           248:        if(pts->y > ymax)
        !           249:             ymax = pts->y;
        !           250: 
        !           251:         pts++;
        !           252:     }
        !           253: 
        !           254:     *by = ROUNDTOINT(ymin);
        !           255:     *ty = (int) ceil(ymax);
        !           256:     return(ptMin-ptsStart);
        !           257: }

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