![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mipolycon.c 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 mipolycon.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
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: mipolycon.c,v 1.15 87/09/11 07:18:54 toddb Exp $ */
25: #include "gcstruct.h"
26: #include "pixmap.h"
27: #include "miscanfill.h"
28:
29: /*
30: * convexpoly.c
31: *
32: * Written by Brian Kelleher; Dec. 1985.
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 an extension of Bresenham's
40: * line algorithm with y as the major axis.
41: * For a derivation of the algorithm, see the author of
42: * this code.
43: */
44: void
45: miFillConvexPoly(dst, pgc, count, ptsIn)
46: DrawablePtr dst;
47: GCPtr pgc;
48: int count; /* number of points */
49: DDXPointPtr ptsIn; /* the points */
50: {
51: register int xl, xr; /* x vals of left and right edges */
52: register int dl, dr; /* decision variables */
53: register int ml, m1l; /* left edge slope and slope+1 */
54: int mr, m1r; /* right edge slope and slope+1 */
55: int incr1l, incr2l; /* left edge error increments */
56: int incr1r, incr2r; /* right edge error increments */
57: int dy; /* delta y */
58: int y; /* current scanline */
59: int left, right; /* indices to first endpoints */
60: int i; /* loop counter */
61: int nextleft, nextright; /* indices to second endpoints */
62: DDXPointPtr ptsOut, FirstPoint; /* output buffer */
63: int *width, *FirstWidth; /* output buffer */
64: int imin; /* index of smallest vertex (in y) */
65: int ymin; /* y-extents of polygon */
66: int ymax;
67:
68: /*
69: * find leftx, bottomy, rightx, topy, and the index
70: * of bottomy. Also translate the points.
71: */
72: imin = getPolyYBounds(ptsIn, count, &ymin, &ymax);
73:
74: dy = ymax - ymin + 1;
75: ptsOut = FirstPoint = (DDXPointPtr )ALLOCATE_LOCAL(sizeof(DDXPointRec)*dy);
76: width = FirstWidth = (int *)ALLOCATE_LOCAL(sizeof(int) * dy);
77: if(!ptsOut || !width)
78: {
79: DEALLOCATE_LOCAL(width);
80: DEALLOCATE_LOCAL(ptsOut);
81: return;
82: }
83:
84: if ((count < 3) || (dy < 0))
85: {
86: DEALLOCATE_LOCAL(width);
87: DEALLOCATE_LOCAL(ptsOut);
88: return;
89: }
90:
91: nextleft = nextright = imin;
92: y = ptsIn[nextleft].y;
93:
94: /*
95: * loop through all edges of the polygon
96: */
97: do {
98: /*
99: * add a left edge if we need to
100: */
101: if (ptsIn[nextleft].y == y) {
102: left = nextleft;
103:
104: /*
105: * find the next edge, considering the end
106: * conditions of the array.
107: */
108: nextleft++;
109: if (nextleft >= count)
110: nextleft = 0;
111:
112: /*
113: * now compute all of the random information
114: * needed to run the iterative algorithm.
115: */
116: BRESINITPGON(ptsIn[nextleft].y-ptsIn[left].y,
117: ptsIn[left].x,ptsIn[nextleft].x,
118: xl, dl, ml, m1l, incr1l, incr2l);
119: }
120:
121: /*
122: * add a right edge if we need to
123: */
124: if (ptsIn[nextright].y == y) {
125: right = nextright;
126:
127: /*
128: * find the next edge, considering the end
129: * conditions of the array.
130: */
131: nextright--;
132: if (nextright < 0)
133: nextright = count-1;
134:
135: /*
136: * now compute all of the random information
137: * needed to run the iterative algorithm.
138: */
139: BRESINITPGON(ptsIn[nextright].y-ptsIn[right].y,
140: ptsIn[right].x,ptsIn[nextright].x,
141: xr, dr, mr, m1r, incr1r, incr2r);
142: }
143:
144: /*
145: * generate scans to fill while we still have
146: * a right edge as well as a left edge.
147: */
148: i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
149: /* in case we're called with non-convex polygon */
150: if(i < 0)
151: {
152: DEALLOCATE_LOCAL(FirstWidth);
153: DEALLOCATE_LOCAL(FirstPoint);
154: return;
155: }
156: while (i-- > 0)
157: {
158: ptsOut->y = y;
159:
160: /*
161: * reverse the edges if necessary
162: */
163: if (xl < xr)
164: {
165: *(width++) = xr - xl;
166: (ptsOut++)->x = xl;
167: }
168: else
169: {
170: *(width++) = xl - xr;
171: (ptsOut++)->x = xr;
172: }
173: y++;
174:
175: /* increment down the edges */
176: BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
177: BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
178: }
179: } while (y != ymax);
180:
181: /*
182: * Finally, fill the <remaining> spans
183: */
184: (*pgc->FillSpans)(dst, pgc,
185: ptsOut-FirstPoint,FirstPoint,FirstWidth,
186: 1);
187: DEALLOCATE_LOCAL(FirstWidth);
188: DEALLOCATE_LOCAL(FirstPoint);
189: }
190:
191:
192: /*
193: * Find the index of the point with the smallest y.
194: */
195: static
196: int
197: getPolyYBounds(pts, n, by, ty)
198: DDXPointPtr pts;
199: int n;
200: int *by, *ty;
201: {
202: register DDXPointPtr ptMin;
203: int ymin, ymax;
204: DDXPointPtr ptsStart = pts;
205:
206: ptMin = pts;
207: ymin = ymax = (pts++)->y;
208:
209: while (--n > 0) {
210: if (pts->y < ymin)
211: {
212: ptMin = pts;
213: ymin = pts->y;
214: }
215: if(pts->y > ymax)
216: ymax = pts->y;
217:
218: pts++;
219: }
220:
221: *by = ymin;
222: *ty = ymax;
223: return(ptMin-ptsStart);
224: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.