Return to poly.h CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X

Annotation of researchv9/X11/src/X.V11R1/lib/X/poly.h, revision 1.1

1.1     ! root        1: /* $Header: poly.h,v 1.1 87/09/11 08:15:38 toddb Exp $ */
        !             2: /************************************************************************
        !             3: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
        !             4: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
        !             5: 
        !             6:                         All Rights Reserved
        !             7: 
        !             8: Permission to use, copy, modify, and distribute this software and its 
        !             9: documentation for any purpose and without fee is hereby granted, 
        !            10: provided that the above copyright notice appear in all copies and that
        !            11: both that copyright notice and this permission notice appear in 
        !            12: supporting documentation, and that the names of Digital or MIT not be
        !            13: used in advertising or publicity pertaining to distribution of the
        !            14: software without specific, written prior permission.  
        !            15: 
        !            16: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
        !            17: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
        !            18: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
        !            19: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
        !            20: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
        !            21: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
        !            22: SOFTWARE.
        !            23: 
        !            24: ************************************************************************/
        !            25: #define NULL 0
        !            26: 
        !            27: 
        !            28: /*
        !            29:  *     This file contains a few macros to help track
        !            30:  *     the edge of a filled object.  The object is assumed
        !            31:  *     to be filled in scanline order, and thus the
        !            32:  *     algorithm used is an extension of Bresenham's line
        !            33:  *     drawing algorithm which assumes that y is always the
        !            34:  *     major axis.
        !            35:  *     Since these pieces of code are the same for any filled shape,
        !            36:  *     it is more convenient to gather the library in one
        !            37:  *     place, but since these pieces of code are also in
        !            38:  *     the inner loops of output primitives, procedure call
        !            39:  *     overhead is out of the question.
        !            40:  *     See the author for a derivation if needed.
        !            41:  */
        !            42: 
        !            43: 
        !            44: /*
        !            45:  *  In scan converting polygons, we want to choose those pixels
        !            46:  *  which are inside the polygon.  Thus, we add .5 to the starting
        !            47:  *  x coordinate for both left and right edges.  Now we choose the
        !            48:  *  first pixel which is inside the pgon for the left edge and the
        !            49:  *  first pixel which is outside the pgon for the right edge.
        !            50:  *  Draw the left pixel, but not the right.
        !            51:  *
        !            52:  *  How to add .5 to the starting x coordinate:
        !            53:  *      If the edge is moving to the right, then subtract dy from the
        !            54:  *  error term from the general form of the algorithm.
        !            55:  *      If the edge is moving to the left, then add dy to the error term.
        !            56:  *
        !            57:  *  The reason for the difference between edges moving to the left
        !            58:  *  and edges moving to the right is simple:  If an edge is moving
        !            59:  *  to the right, then we want the algorithm to flip immediately.
        !            60:  *  If it is moving to the left, then we don't want it to flip until
        !            61:  *  we traverse an entire pixel.
        !            62:  */
        !            63: #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
        !            64:     int dx;      /* local storage */ \
        !            65: \
        !            66:     /* \
        !            67:      *  if the edge is horizontal, then it is ignored \
        !            68:      *  and assumed not to be processed.  Otherwise, do this stuff. \
        !            69:      */ \
        !            70:     if ((dy) != 0) { \
        !            71:         xStart = (x1); \
        !            72:         dx = (x2) - xStart; \
        !            73:         if (dx < 0) { \
        !            74:             m = dx / (dy); \
        !            75:             m1 = m - 1; \
        !            76:             incr1 = -2 * dx + 2 * (dy) * m1; \
        !            77:             incr2 = -2 * dx + 2 * (dy) * m; \
        !            78:             d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
        !            79:         } else { \
        !            80:             m = dx / (dy); \
        !            81:             m1 = m + 1; \
        !            82:             incr1 = 2 * dx - 2 * (dy) * m1; \
        !            83:             incr2 = 2 * dx - 2 * (dy) * m; \
        !            84:             d = -2 * m * (dy) + 2 * dx; \
        !            85:         } \
        !            86:     } \
        !            87: }
        !            88: 
        !            89: #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
        !            90:     if (m1 > 0) { \
        !            91:         if (d > 0) { \
        !            92:             minval += m1; \
        !            93:             d += incr1; \
        !            94:         } \
        !            95:         else { \
        !            96:             minval += m; \
        !            97:             d += incr2; \
        !            98:         } \
        !            99:     } else {\
        !           100:         if (d >= 0) { \
        !           101:             minval += m1; \
        !           102:             d += incr1; \
        !           103:         } \
        !           104:         else { \
        !           105:             minval += m; \
        !           106:             d += incr2; \
        !           107:         } \
        !           108:     } \
        !           109: }
        !           110: 
        !           111: 
        !           112: /*
        !           113:  *     This structure contains all of the information needed
        !           114:  *     to run the bresenham algorithm.
        !           115:  *     The variables may be hardcoded into the declarations
        !           116:  *     instead of using this structure to make use of
        !           117:  *     register declarations.
        !           118:  */
        !           119: typedef struct {
        !           120:     int minor_axis;    /* minor axis        */
        !           121:     int d;             /* decision variable */
        !           122:     int m, m1;         /* slope and slope+1 */
        !           123:     int incr1, incr2;  /* error increments */
        !           124: } BRESINFO;
        !           125: 
        !           126: 
        !           127: #define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
        !           128:        BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
        !           129:                      bres.m, bres.m1, bres.incr1, bres.incr2)
        !           130: 
        !           131: #define BRESINCRPGONSTRUCT(bres) \
        !           132:         BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
        !           133: 
        !           134: 
        !           135: 
        !           136: /*
        !           137:  *     These are the data structures needed to scan
        !           138:  *     convert regions.  Two different scan conversion
        !           139:  *     methods are available -- the even-odd method, and
        !           140:  *     the winding number method.
        !           141:  *     The even-odd rule states that a point is inside
        !           142:  *     the polygon if a ray drawn from that point in any
        !           143:  *     direction will pass through an odd number of
        !           144:  *     path segments.
        !           145:  *     By the winding number rule, a point is decided
        !           146:  *     to be inside the polygon if a ray drawn from that
        !           147:  *     point in any direction passes through a different
        !           148:  *     number of clockwise and counter-clockwise path
        !           149:  *     segments.
        !           150:  *
        !           151:  *     These data structures are adapted somewhat from
        !           152:  *     the algorithm in (Foley/Van Dam) for scan converting
        !           153:  *     polygons.
        !           154:  *     The basic algorithm is to start at the top (smallest y)
        !           155:  *     of the polygon, stepping down to the bottom of
        !           156:  *     the polygon by incrementing the y coordinate.  We
        !           157:  *     keep a list of edges which the current scanline crosses,
        !           158:  *     sorted by x.  This list is called the Active Edge Table (AET)
        !           159:  *     As we change the y-coordinate, we update each entry in 
        !           160:  *     in the active edge table to reflect the edges new xcoord.
        !           161:  *     This list must be sorted at each scanline in case
        !           162:  *     two edges intersect.
        !           163:  *     We also keep a data structure known as the Edge Table (ET),
        !           164:  *     which keeps track of all the edges which the current
        !           165:  *     scanline has not yet reached.  The ET is basically a
        !           166:  *     list of ScanLineList structures containing a list of
        !           167:  *     edges which are entered at a given scanline.  There is one
        !           168:  *     ScanLineList per scanline at which an edge is entered.
        !           169:  *     When we enter a new edge, we move it from the ET to the AET.
        !           170:  *
        !           171:  *     From the AET, we can implement the even-odd rule as in
        !           172:  *     (Foley/Van Dam).
        !           173:  *     The winding number rule is a little trickier.  We also
        !           174:  *     keep the EdgeTableEntries in the AET linked by the
        !           175:  *     nextWETE (winding EdgeTableEntry) link.  This allows
        !           176:  *     the edges to be linked just as before for updating
        !           177:  *     purposes, but only uses the edges linked by the nextWETE
        !           178:  *     link as edges representing spans of the polygon to
        !           179:  *     drawn (as with the even-odd rule).
        !           180:  */
        !           181: 
        !           182: /*
        !           183:  * for the winding number rule
        !           184:  */
        !           185: #define CLOCKWISE          1
        !           186: #define COUNTERCLOCKWISE  -1 
        !           187: 
        !           188: typedef struct _EdgeTableEntry {
        !           189:      int ymax;             /* ycoord at which we exit this edge. */
        !           190:      BRESINFO bres;        /* Bresenham info to run the edge     */
        !           191:      struct _EdgeTableEntry *next;       /* next in the list     */
        !           192:      struct _EdgeTableEntry *back;       /* for insertion sort   */
        !           193:      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
        !           194:      int ClockWise;        /* flag for winding number rule       */
        !           195: } EdgeTableEntry;
        !           196: 
        !           197: 
        !           198: typedef struct _ScanLineList{
        !           199:      int scanline;              /* the scanline represented */
        !           200:      EdgeTableEntry *edgelist;  /* header node              */
        !           201:      struct _ScanLineList *next;  /* next in the list       */
        !           202: } ScanLineList;
        !           203: 
        !           204: 
        !           205: typedef struct {
        !           206:      int ymax;                 /* ymax for the polygon     */
        !           207:      int ymin;                 /* ymin for the polygon     */
        !           208:      ScanLineList scanlines;   /* header node              */
        !           209: } EdgeTable;
        !           210: 
        !           211: 
        !           212: /*
        !           213:  * Here is a struct to help with storage allocation
        !           214:  * so we can allocate a big chunk at a time, and then take
        !           215:  * pieces from this heap when we need to.
        !           216:  */
        !           217: #define SLLSPERBLOCK 25
        !           218: 
        !           219: typedef struct _ScanLineListBlock {
        !           220:      ScanLineList SLLs[SLLSPERBLOCK];
        !           221:      struct _ScanLineListBlock *next;
        !           222: } ScanLineListBlock;
        !           223: 
        !           224: 
        !           225: 
        !           226: /*
        !           227:  *
        !           228:  *     a few macros for the inner loops of the fill code where
        !           229:  *     performance considerations don't allow a procedure call.
        !           230:  *
        !           231:  *     Evaluate the given edge at the given scanline.
        !           232:  *     If the edge has expired, then we leave it and fix up
        !           233:  *     the active edge table; otherwise, we increment the
        !           234:  *     x value to be ready for the next scanline.
        !           235:  *     The winding number rule is in effect, so we must notify
        !           236:  *     the caller when the edge has been removed so he
        !           237:  *     can reorder the Winding Active Edge Table.
        !           238:  */
        !           239: #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
        !           240:    if (pAET->ymax == y) {          /* leaving this edge */ \
        !           241:       pPrevAET->next = pAET->next; \
        !           242:       pAET = pPrevAET->next; \
        !           243:       fixWAET = 1; \
        !           244:       if (pAET) \
        !           245:          pAET->back = pPrevAET; \
        !           246:    } \
        !           247:    else { \
        !           248:       BRESINCRPGONSTRUCT(pAET->bres); \
        !           249:       pPrevAET = pAET; \
        !           250:       pAET = pAET->next; \
        !           251:    } \
        !           252: }
        !           253: 
        !           254: 
        !           255: /*
        !           256:  *     Evaluate the given edge at the given scanline.
        !           257:  *     If the edge has expired, then we leave it and fix up
        !           258:  *     the active edge table; otherwise, we increment the
        !           259:  *     x value to be ready for the next scanline.
        !           260:  *     The even-odd rule is in effect.
        !           261:  */
        !           262: #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
        !           263:    if (pAET->ymax == y) {          /* leaving this edge */ \
        !           264:       pPrevAET->next = pAET->next; \
        !           265:       pAET = pPrevAET->next; \
        !           266:       if (pAET) \
        !           267:          pAET->back = pPrevAET; \
        !           268:    } \
        !           269:    else { \
        !           270:       BRESINCRPGONSTRUCT(pAET->bres); \
        !           271:       pPrevAET = pAET; \
        !           272:       pAET = pAET->next; \
        !           273:    } \
        !           274: }

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