![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mipoly.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi|
Return to mipoly.h CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
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.