![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to poly.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 / lib / X|
Return to poly.h CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / lib / X |
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.