Return to mipoly.h CVS log

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

Annotation of researchv9/X11/src/X.V11R1/server/ddx/mi/mipoly.h, revision 1.1

1.1     ! root        1: /* $Header: mipoly.h,v 1.1 87/09/11 07:20:03 toddb Exp $ */
        !             2: /*
        !             3:  *     fill.h
        !             4:  *
        !             5:  *     Created by Brian Kelleher; Oct 1985
        !             6:  *
        !             7:  *     Include file for filled polygon routines.
        !             8:  *
        !             9:  *     These are the data structures needed to scan
        !            10:  *     convert regions.  Two different scan conversion
        !            11:  *     methods are available -- the even-odd method, and
        !            12:  *     the winding number method.
        !            13:  *     The even-odd rule states that a point is inside
        !            14:  *     the polygon if a ray drawn from that point in any
        !            15:  *     direction will pass through an odd number of
        !            16:  *     path segments.
        !            17:  *     By the winding number rule, a point is decided
        !            18:  *     to be inside the polygon if a ray drawn from that
        !            19:  *     point in any direction passes through a different
        !            20:  *     number of clockwise and counter-clockwise path
        !            21:  *     segments.
        !            22:  *
        !            23:  *     These data structures are adapted somewhat from
        !            24:  *     the algorithm in (Foley/Van Dam) for scan converting
        !            25:  *     polygons.
        !            26:  *     The basic algorithm is to start at the top (smallest y)
        !            27:  *     of the polygon, stepping down to the bottom of
        !            28:  *     the polygon by incrementing the y coordinate.  We
        !            29:  *     keep a list of edges which the current scanline crosses,
        !            30:  *     sorted by x.  This list is called the Active Edge Table (AET)
        !            31:  *     As we change the y-coordinate, we update each entry in 
        !            32:  *     in the active edge table to reflect the edges new xcoord.
        !            33:  *     This list must be sorted at each scanline in case
        !            34:  *     two edges intersect.
        !            35:  *     We also keep a data structure known as the Edge Table (ET),
        !            36:  *     which keeps track of all the edges which the current
        !            37:  *     scanline has not yet reached.  The ET is basically a
        !            38:  *     list of ScanLineList structures containing a list of
        !            39:  *     edges which are entered at a given scanline.  There is one
        !            40:  *     ScanLineList per scanline at which an edge is entered.
        !            41:  *     When we enter a new edge, we move it from the ET to the AET.
        !            42:  *
        !            43:  *     From the AET, we can implement the even-odd rule as in
        !            44:  *     (Foley/Van Dam).
        !            45:  *     The winding number rule is a little trickier.  We also
        !            46:  *     keep the EdgeTableEntries in the AET linked by the
        !            47:  *     nextWETE (winding EdgeTableEntry) link.  This allows
        !            48:  *     the edges to be linked just as before for updating
        !            49:  *     purposes, but only uses the edges linked by the nextWETE
        !            50:  *     link as edges representing spans of the polygon to
        !            51:  *     drawn (as with the even-odd rule).
        !            52:  */
        !            53: 
        !            54: /*
        !            55:  * for the winding number rule
        !            56:  */
        !            57: #define CLOCKWISE          1
        !            58: #define COUNTERCLOCKWISE  -1 
        !            59: 
        !            60: typedef struct _EdgeTableEntry {
        !            61:      int ymax;             /* ycoord at which we exit this edge. */
        !            62:      BRESINFO bres;        /* Bresenham info to run the edge     */
        !            63:      struct _EdgeTableEntry *next;       /* next in the list     */
        !            64:      struct _EdgeTableEntry *back;       /* for insertion sort   */
        !            65:      struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
        !            66:      int ClockWise;        /* flag for winding number rule       */
        !            67: } EdgeTableEntry;
        !            68: 
        !            69: 
        !            70: typedef struct _ScanLineList{
        !            71:      int scanline;              /* the scanline represented */
        !            72:      EdgeTableEntry *edgelist;  /* header node              */
        !            73:      struct _ScanLineList *next;  /* next in the list       */
        !            74: } ScanLineList;
        !            75: 
        !            76: 
        !            77: typedef struct {
        !            78:      int ymax;                 /* ymax for the polygon     */
        !            79:      int ymin;                 /* ymin for the polygon     */
        !            80:      ScanLineList scanlines;   /* header node              */
        !            81: } EdgeTable;
        !            82: 
        !            83: 
        !            84: /*
        !            85:  * Here is a struct to help with storage allocation
        !            86:  * so we can allocate a big chunk at a time, and then take
        !            87:  * pieces from this heap when we need to.
        !            88:  */
        !            89: #define SLLSPERBLOCK 25
        !            90: 
        !            91: typedef struct _ScanLineListBlock {
        !            92:      ScanLineList SLLs[SLLSPERBLOCK];
        !            93:      struct _ScanLineListBlock *next;
        !            94: } ScanLineListBlock;
        !            95: 
        !            96: /*
        !            97:  * number of points to buffer before sending them off
        !            98:  * to scanlines() :  Must be an even number
        !            99:  */
        !           100: #define NUMPTSTOBUFFER 200
        !           101: 
        !           102: 
        !           103: /*
        !           104:  *
        !           105:  *     a few macros for the inner loops of the fill code where
        !           106:  *     performance considerations don't allow a procedure call.
        !           107:  *
        !           108:  *     Evaluate the given edge at the given scanline.
        !           109:  *     If the edge has expired, then we leave it and fix up
        !           110:  *     the active edge table; otherwise, we increment the
        !           111:  *     x value to be ready for the next scanline.
        !           112:  *     The winding number rule is in effect, so we must notify
        !           113:  *     the caller when the edge has been removed so he
        !           114:  *     can reorder the Winding Active Edge Table.
        !           115:  */
        !           116: #define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
        !           117:    if (pAET->ymax == y) {          /* leaving this edge */ \
        !           118:       pPrevAET->next = pAET->next; \
        !           119:       pAET = pPrevAET->next; \
        !           120:       fixWAET = 1; \
        !           121:       if (pAET) \
        !           122:          pAET->back = pPrevAET; \
        !           123:    } \
        !           124:    else { \
        !           125:       BRESINCRPGONSTRUCT(pAET->bres); \
        !           126:       pPrevAET = pAET; \
        !           127:       pAET = pAET->next; \
        !           128:    } \
        !           129: }
        !           130: 
        !           131: 
        !           132: /*
        !           133:  *     Evaluate the given edge at the given scanline.
        !           134:  *     If the edge has expired, then we leave it and fix up
        !           135:  *     the active edge table; otherwise, we increment the
        !           136:  *     x value to be ready for the next scanline.
        !           137:  *     The even-odd rule is in effect.
        !           138:  */
        !           139: #define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
        !           140:    if (pAET->ymax == y) {          /* leaving this edge */ \
        !           141:       pPrevAET->next = pAET->next; \
        !           142:       pAET = pPrevAET->next; \
        !           143:       if (pAET) \
        !           144:          pAET->back = pPrevAET; \
        !           145:    } \
        !           146:    else { \
        !           147:       BRESINCRPGONSTRUCT(pAET->bres); \
        !           148:       pPrevAET = pAET; \
        !           149:       pAET = pAET->next; \
        !           150:    } \
        !           151: }

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